时间限制:1000ms
单点时限:1000ms
内存限制:256MB
- 样例输入
-
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
描述
给出平面上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条线段是否恰好围成矩形。
这道题目思路简单。首先判断给出的四条线段能不能组成四边形,如果可以,在判断这个四边形是不是矩形。
判断是不是四边形:
输入了四条线段,总共有八个点。如果这八个点中,两两重合,总共有四个点,那么一定是一个四边形。判断八个点是不是两两重合,用set即可。set插入八个点,如果大小为四,那么就是两两重合。
一个四边形,如果一条边和另外三条边要么平行,要么垂直,那么就是矩形。判断平行或垂直,用斜率即可。
#include<iostream> #include<set> struct Point{ int x; int y; bool operator<(const Point& p2)const { //优先判断横坐标 if(x<p2.x||(x==p2.x&&y<p2.y)) return true; return false; } bool operator==(const Point& p2) const { return (x==p2.x&&y==p2.y); } }; struct Line{ Point p1; Point p2; }; //判断是不是四个点 bool JudgePoint(Line *L) { std::set<Point> S; for(int i=0;i<4;++i) { S.insert(L[i].p1); S.insert(L[i].p2); } return (S.size()==4); } bool JudgeRect(Line *L) { for(int i=1;i<4;++i) { //判断是不是垂直 if((L[0].p1.y-L[0].p2.y)*(L[i].p1.y-L[i].p2.y)==-(L[0].p1.x-L[0].p2.x)*(L[i].p1.x-L[i].p2.x)) continue; //判断是不是平行 if((L[0].p1.y-L[0].p2.y)*(L[i].p1.x-L[i].p2.x)==(L[0].p1.x-L[0].p2.x)*(L[i].p1.y-L[i].p2.y)) continue; return false; } return true; } int main() { int n; Line L[4]; std::cin>>n; while(n--) { for(int i=0;i<4;++i) { std::cin>>L[i].p1.x>>L[i].p1.y>>L[i].p2.x>>L[i].p2.y; } //判断是不是四个点 if(!JudgePoint(L)) { std::cout<<"NO"<<std::endl; continue; } if(!JudgeRect(L)) { std::cout<<"NO"<<std::endl; continue; } std::cout<<"YES"<<std::endl; } }