hdu 5533 Dancing Stars on Me 【2015ACM/ICPC亚洲区长春站-重现赛(感谢东北师大)】
发布日期:2021-08-21 08:23:53
浏览次数:4
分类:技术文章
本文共 2573 字,大约阅读时间需要 8 分钟。
Dancing Stars on Me
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others) Total Submission(s): 370 Accepted Submission(s): 222 Problem Description
The sky was brushed clean by the wind and the stars were cold in a black sky. What a wonderful night. You observed that, sometimes the stars can form a regular polygon in the sky if we connect them properly. You want to record these moments by your smart camera. Of course, you cannot stay awake all night for capturing. So you decide to write a program running on the smart camera to check whether the stars can form a regular polygon and capture these moments automatically. Formally, a regular polygon is a convex polygon whose angles are all equal and all its sides have the same length. The area of a regular polygon must be nonzero. We say the stars can form a regular polygon if they are exactly the vertices of some regular polygon. To simplify the problem, we project the sky to a two-dimensional plane here, and you just need to check whether the stars can form a regular polygon in this plane.
Input
The first line contains a integer T indicating the total number of test cases. Each test case begins with an integer n, denoting the number of stars in the sky. Following n lines, each contains 2 integers xi,yi, describe the coordinates of n stars. 1≤T≤300 3≤n≤100 −10000≤xi,yi≤10000 All coordinates are distinct.
Output
For each test case, please output "`YES`" if the stars can form a regular polygon. Otherwise, output "`NO`" (both without quotes).
Sample Input
3 3 0 0 1 1 1 0 4 0 0 0 1 1 0 1 1 5 0 0 0 1 0 2 2 2 2 0
Sample Output
NO YES NO
题目大意:
就是判断给出的坐标是不是能够组成一个正 m 边形。。。
解题思路:
首先要知道,只有当 m == 4 的时候才有可能是正方形,别的都不可能(因为坐标是整数)。。。
所以只要判断是不是正方形就 ok 了, 可是给出的坐标不一定是按照顺序给出的,所以要判断一下,让他按照顺序给出。。。
上代码:
#include#include #include #include #include #include #include #include #include using namespace std;#define MM(a) memset(a,0,sizeof(a))typedef long long LL;typedef unsigned long long ULL;const int maxn = 1e3+5;const int mod = 1000000007;const double eps = 1e-7;LL gcd(LL a, LL b){ if(b == 0) return a; return gcd(b, a%b);}struct node{ int x, y;} arr[maxn];int xx[maxn], yy[maxn];bool cmp(node a, node b){ if(a.y != b.y) return a.x < b.x; return a.y < a.y;}int main(){ int T, m; cin>>T; while(T--) { cin>>m; for(int i=0; i >arr[i].x>>arr[i].y; if(m != 4) puts("NO"); else { sort(arr, arr+4, cmp); if(arr[1].y < arr[0].y) swap(arr[1], arr[2]); swap(arr[2], arr[3]); /*for(int i=0; i<4; i++) cout< <<" "< <
转载地址:https://blog.csdn.net/weixin_33713503/article/details/90688101 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
表示我来过!
[***.240.166.169]2024年04月10日 04时56分44秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
JPA 默认值配置
2019-04-25
myeclipse 的 maven工程报错或pom.xml头报错解决办法
2019-04-25
反向Ajax,第2部分:WebSocket
2019-04-25
反向Ajax,第1部分:Comet介绍
2019-04-25
反向Ajax,第3部分:Web服务器和Socket.IO
2019-04-25
反向Ajax,第4部分:Atmosphere和CometD
2019-04-25
反向Ajax,第5部分:事件驱动的Web开发
2019-04-25
Servlet3.0新特性&动态代理
2019-04-25
servlet3 实现请求异步处理
2019-04-25
java线程管理利器:java.util.current的用法举例
2019-04-25
native2ascii.exe的使用
2019-04-25
docker-machine的安装
2019-04-25
用docker-machine创建虚拟主机
2019-04-25
spring mvc 4 + swagger2
2019-04-25
Jenkins之持续构建
2019-04-25
sonarqube 启动不了,异常提示:远程主机强迫关闭了一个现有的连接。
2019-04-25
jenkins 参数化构建作业
2019-04-25
容器div内容超出后,自动出现滚动条
2019-04-25
RDLC报表相关
2019-04-25