hihocoder #1040 矩形判断（计算几何问题 给8个点的坐标，能否成为一个矩形 【模板思路】）
2024-10-18 20:00:24
#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
算法分析：我没有计算几何的模板，这道计算几何基础题就只能自己敲！ 要完成这道题：首先需要知道一下知识点！
1.一个面积大于0的矩形必会有4个互不相同的顶点
2.四条边的权值相等（即邻边相等，四边等边平行四边形）或者 边的权值只有两种值（即临边不相等，而对边相等的平行四边形）
3.最后判断是不是有个角是直角（只要找到两个边互相垂直就行了， 即向量的点积运算 ） 注意：我在算法的实现的过程中用到了STL的set结构，需要注意的一点是：如果要将一个结构体引入set集合，则必须要对所有结构体的元素
进行一种重载运算符的书写。否则就会导致数据的丢失！
比如：我插入了点（0, 0），再去插入点(0，1)，就可能将丢失（0, 1）点。注意！#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <algorithm>
#define eps 1e-8
#define PI acos(-1.0) using namespace std; struct pointer
{
int x, y;
bool operator <(const pointer&dd)const{
if(x==dd.x){
return y<dd.y;
}
return x<dd.x;
}
}u, v; set<pointer>a; //点集
set<int>b; //边集 int line(pointer a, pointer b)
{
return ((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}
struct vect
{
int x, y;
}c[4]; int main()
{
int t;
int i, j;
scanf("%d", &t);
while(t--)
{
if(!a.empty()) a.clear();
if(!b.empty()) b.clear();
for(i=0; i<4; i++)
{
scanf("%d %d %d %d", &u.x, &u.y, &v.x, &v.y ); //读入一条边
a.insert(u); a.insert(v);
b.insert(line(u, v));
c[i].x = u.x-v.x;
c[i].y = u.y-v.y; //构建向量
}
if(a.size()!=4){
set<pointer>::iterator it=a.begin(); /* while(it!=a.end())
{
printf("%d--%d ", it->x, it->y ); it++;
} */
//printf("*******%d\n", a.size()); printf("NO\n"); continue;
}
if(b.size()>2){ //==1是正方形 ==2是长方形
printf("NO\n"); continue;
}
//如果这个四边形只有四个点， 并且只有一个或两个不同大小的边
bool flag=false;
for(i=0; i<4; i++)
{
for(j=0; j<4; j++){
if(i!=j){
if((c[i].x*c[j].x + c[i].y*c[j].y) ==0 )
{
flag=true; break;
}
}
}
if(flag==true) break;
}
if(flag==true ) printf("YES\n");
else printf("NO\n");
}
return 0;
}
最新文章
- 初识SQL Server Integration Service
- JavaSE——TCP网络编程（二）
- Block 块
- ios中xib的使用介绍
- 插头DP题目泛做（为了对应WYD的课件）
- cocos2d-x教程1 hello world
- 树莓派linux驱动学习之hello world
- 多项式相乘（C语言）
- MVC与Validate验证提示的样式修改
- 如何在Android中添加系统服务
- Xpath语法学习
- Python爬虫进阶(Scrapy框架爬虫)
- Druid的简介
- 置信区间-显著性-P-值
- Linux 登陆配置读取顺序
- 广播频道-BroadcastChannel
- 机器学习:K-Means/K-Means++
- HDU1007.Quoit Design
- Excel vba map/dictionary
- 查看Windows系统信息