hihoCoder 1040 矩形判断（计算几何）

http://hihocoder.com/problemset/problem/1040

首先判断四条线段是否相交，给出八个点，如果有一些点重合，并且不同坐标的点只有4个的话，表示可以构成四边形。

然后判断每一条线段与其他线段树平行或者垂直，每一条线段都和其他线段平行或垂直的话就能构成矩形。

平行或相交可以用斜率计算，注意斜率不存在或者等于0的情况。

平行斜率相等，垂直的话斜率相乘等于-1，或者一个不存在一个为0.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
double maxn = 1000000;
struct point
{
    int x,y;
}p[10];

bool check()
{
    int m=8;
    for(int i=0;i<8;i++)
        for(int j=i+1;j<8;j++)
        if(p[i].x==p[j].x&&p[i].y==p[j].y) m--;
    if(m==4) return true;
    return false;
}

double solve(point a,point b)
{
    if(a.x==b.x) return maxn;
    else if(a.y==b.y) return 0;
    else return 1.0*(a.y-b.y)/(a.x-b.x);
}
int main()
{
    //freopen("a.txt","r",stdin);
    int t;
    double k[5];
    scanf("%d",&t);
    while(t--)
    {
        for(int i=0;i<8;i++) scanf("%d%d",&p[i].x,&p[i].y);
        if(check()==0) {printf("NO\n");continue;}  //检测是否构成四边形
        memset(k,0,sizeof(k));
        int z=0;
        for(int i=0;i<7;i+=2)
        {
            k[z++]=solve(p[i],p[i+1]); //计算每一条线段的斜率
           // printf("%.3lf\n",k[z-1]);
        }
        bool flag=0;
        for(int i=0;i<4;i++)
        {     //判断两条线段的关系 
            for(int j=0;j<4;j++)
            {
                if((k[i]==k[j])||(k[i]==maxn&&k[j]==0)||(k[i]==0&&k[j]==maxn)||(k[i]*k[j]==-1)) continue;
                else {flag=1;break;}
            }
            if(flag) break;
        }
        if(flag) printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}