217四边形的秘密.docx

解题思路

本题是关于矩形判定的计算几何问题，需要注意的是，输入的四条边不一定按照顺序输入。我们需要先判断输入的四条边能否构成矩形，如果能，就判断这个矩形是否是正面积的矩形。

因为题目要求门的四个边分别平行于坐标轴，而一个矩形有两条平行于?x?轴的边和两条平行于?y?轴的边，所以我们可以先判断每条边是否平行于坐标轴，如果不是，那么这四条边就不能构成一个矩形。具体实现方法是遍历输入的四条边，如果横坐标和纵坐标都不同，那么就说明这条边不与坐标轴平行，不能构成矩形。

同时，一个矩形的两条平行于?x?轴的边长度相等，两条平行于?y?轴的边长度也相等，因此我们还需要统计每条边的长度，如果有两条长度不相等的边，那么这四条边也不能构成一个矩形。如果四条边能构成矩形，接下来我们需要判断这个矩形是否是正面积的矩形。一个矩形的面积是它的长和宽的乘积，因为这个矩形的边平行于坐标轴，所以矩形的长和宽可以根据边的坐标计算得到。

一个更快的方法是，在判断了有两对分别平行坐标轴的线段后，由于只输入了?8?个坐标，但是矩形有?4?个顶点，那么每个顶点出现了有且只有?2?次。

遍历输入的四条边需要?O(1)?的时间复杂度，统计每条边的长度和检查每个点的出现次数也需要O(1)?的时间复杂度，因此总的时间复杂度是?O(1)。

AC_Code

C++

#includebits/stdc++.h

usingnamespacestd;

typedefpairint,intpii;

vectorpiip;

intmain()

{

boolflag=true;

mappii,intmp;

intx1,x2,y1,y2;

intpx=0,py=0;

for(inti=0;i4;i++)

{

cinx1y1x2y2;

if(x1!=x2y1!=y2)flag=false;

elseif(x1==x2)px++;

elseif(y1==y2)py++;

elseflag=false;

mp[{x1,y1}]++;

mp[{x2,y2}]++;

p.push_back({x2,y2});

p.push_back({x1,y1});

}

if(px!=2||py!=2)flag=false;

for(inti=0;ip.size();i++)

{

if(mp[p[i]]!=2)flag=false;

}

if(flag)coutYESendl;

elsecoutNOendl;

return0;

}

Java

importjava.util.ArrayList;

importjava.util.Collections;

importjava.util.Comparator;

importjava.util.List;

importjava.util.Scanner;

publicclassrectangle{

intx,y;

rectangle(intx,inty){

this.x=x;

this.y=y;

}

staticintcompare(rectangler1,rectangler2){

returnr1.x-r2.x==0?r2.y-r1.y:r2.x-r1.x;

}

publicstaticvoidmain(String[]args){

Stringres=YES;

intz1=0;

intz2=0;

Scannersc=newScanner(System.in);

Listrectanglerectangles=newArrayListrectangle();

for(inti=0;i4;i++){

intx1=sc.nextInt();

inty1=sc.nextInt();

intx2=sc.nextInt();

inty2=sc.nextInt();