题目地址：http://hihocoder.com/problemset/problem/1040
时间限制:1000ms
单点时限:1000ms
内存限制:256MB
描述
给出平面上4条线段，判断这4条线段是否恰好围成一个面积大于0的矩形。
输入
输入第一行是一个整数T(1<=T<=100)，代表测试数据的数量。
每组数据包含4行，每行包含4个整数x1, y1, x2, y2 (0 <= x1, y1, x2, y2 <= 100000)；其中(x1, y1), (x2,y2)代表一条线段的两个端点。
输出
每组数据输出一行YES或者NO，表示输入的4条线段是否恰好围成矩形。
样例输入
3
0 0 0 1
1 0 1 1
0 1 1 1
1 0 0 0
0 1 2 3
1 0 3 2
3 2 2 3
1 0 0 1
0 1 1 0
1 0 2 0
2 0 1 1
1 1 0 1
样例输出
YES
YES
NO
Java代码如下：
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Main {public static void main(String[] args) {Scanner in=new Scanner(System.in);int t;t=in.nextInt(); for(int i=0;i<t;i++){Set<String> p=new HashSet<String>();int[][] v=new int[2][4];int[] xc=new int[4];for(int j=0;j<4;j++){int x1,x2,y1,y2;x1=in.nextInt();y1=in.nextInt();x2=in.nextInt();y2=in.nextInt();p.add(x1+"."+y1);p.add(x2+"."+y2);v[0][j]=x2-x1; v[1][j]=y2-y1;xc[j]=(x1+x2)*17+(y1+y2)*19;//hash,判断是否是同一条线段}if(p.size()!=4){System.out.println("PNO");continue;}int flag=0;for(int j=1;j<4;j++){if(v[0][0]*v[0][j]+v[1][0]*v[1][j]==0){
//x1*x2+y1*y2=0;垂直flag+=2;continue;}if(v[0][0]*v[1][j]==v[1][0]*v[0][j]){ //x1*y2==x2*y1; 且x1,x2不是同一条线段if(xc[0]!=xc[j]){flag+=3;}} }System.out.println((flag==7)?"YES":"NO");}}}
思路：用Set存每个点，如果点超过四个直接”NO”,然后把第一条线段分别跟2，3，4条比较，如果有两条垂直，一条平行，就可能是矩形。对于平行的线段，还要判断两条直线是否是同一条线段，写了一个哈希函数来判断是否是同一条直线 xc[j]=(x1+x2)*17+(y1+y2)*19;………………….话说写到这里想到了一个bug，就是如果第二三条线段是相同的就没有判断，这里还是用该老老实实地循环把四个都比较一下。