hihoCoder1040:矩形判断

时间限制: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

思路：

解这道题需要考虑三个问题：1.线段长度是否为零。

                                                    2.线段是否恰好能围成四边形。

                                                    3.该四边形是否为矩形。

判断是否四边形：四条线段共8个端点，只有8个端点两两重合时（即只有四个点），才是四边形。

判断是否矩形：要么证四边形两组对边平行且有一个角为直角，要么证四边形三个角为直角。

方法：

结构体，向量点乘为零。

#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
struct point
{
    int x[20];
    int y[20];
}  po,qo,c;
int main()
{
    int i,t,j,k,w,num;
    cin>>t;
    for(i=0;i<t;i++)
    {
        w=0;
        num=0;
        for(j=0;j<4;j++)
        {
           cin>>po.x[j]>>po.y[j];
           cin>>qo.x[j]>>qo.y[j];
            if(po.x[j]==qo.x[j]&&po.y[j]==qo.y[j])/*判断线段长度是否为零，即线段两端点是否相同。*/
                w=1;
        }
     /*线段是否恰好能围成四边形,判断八个点是不是两两重合*/
        for(j=0;j<4;j++)
            for(k=j+1;k<4;k++)
            if((po.x[j]==qo.x[k]&&po.y[j]==qo.y[k])||(po.x[j]==po.x[k]&&po.y[j]==po.y[k])||(qo.x[j]==qo.x[k]&&qo.y[j]==qo.y[k])||(qo.x[j]==po.x[k]&&qo.y[j]==po.y[k]))
             num++;
        if(w==1)
           {
               cout<<"NO"<<endl;
               continue;
           }
         if(num!=4)
         {
             cout<<"NO"<<endl;
             continue;
         }
      /*去掉八个点中相同的点，最后留下四个不同的端点即为四边形的四个点*/
         for(k=1;k<4;k++)
        {
            if(po.x[0]==qo.x[k]&&po.y[0]==qo.y[k])
            {
                  po.x[1]=po.x[k];
                  po.y[1]=po.y[k];
            }
            else if (po.x[0]==po.x[k]&&po.y[0]==po.y[k])
            {
                po.x[1]=qo.x[k];
                po.y[1]=qo.y[k];
            }
            else if(qo.x[0]==qo.x[k]&&qo.y[0]==qo.y[k])
            {
                qo.x[1]=po.x[k];
                qo.y[1]=po.y[k];
            }
            else if(qo.x[0]==po.x[k]&&qo.y[0]==po.y[k])
            {
                qo.x[1]=qo.x[k];
                qo.y[1]=qo.y[k];
            }
        }
        /*求出四边形四条边的方向向量*/
        c.x[0]=qo.x[0]-po.x[0],c.y[0]=qo.y[0]-po.y[0];
        c.x[1]=po.x[1]-po.x[0],c.y[1]=po.y[1]-po.y[0];
        c.x[2]=qo.x[1]-qo.x[0],c.y[2]=qo.y[1]-qo.y[0];
        c.x[3]=qo.x[1]-po.x[1],c.y[3]=qo.y[1]-po.y[1];
        if((c.x[0]*c.x[1]+c.y[0]*c.y[1]==0)&&(c.x[0]*c.x[2]+c.y[0]*c.y[2]==0)&&(c.x[1]*c.x[3]+c.y[1]*c.y[3]==0))
           cout<<"YES"<<endl;
        else
           cout<<"NO"<<endl;
    }
    return 0;
}