欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

hihoCoder1040:矩形判断

程序员文章站 2022-04-03 16:53:47
...
时间限制: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;
}