Dancing Stars on Me

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1098    Accepted Submission(s): 598

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
 
Source
 
Recommend
hujie   |   We have carefully selected several similar problems for you:       
题意:给你n个点(-1e4<x,y<=1e4),判断这n个点能否组成一个正n边形;
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <set>
#define MM(a) memset(a,0,sizeof(a))
typedef long long ll;
typedef unsigned long long ULL;
const double eps = 1e-12;
const int inf = 0x3f3f3f3f;
const double pi=acos(-1);
using namespace std; struct Point{
int x,y;
void read()
{
scanf("%d%d",&x,&y);
}
}p[105],tubao[105]; int dcmp(double a)
{
if(fabs(a)<eps) return 0;
else if(a>0) return 1;
else return -1;
} Point operator-(Point a,Point b)
{
return (Point){a.x-b.x,a.y-b.y};
} double dis(Point a)
{
return sqrt(a.x*a.x+a.y*a.y);
} double cross(Point a,Point b)
{
return a.x*b.y-b.x*a.y;
} double dot(Point a,Point b)
{
return a.x*b.x+a.y*b.y;
} bool cmp(Point a,Point b)
{
if(a.x!=b.x) return a.x<b.x;
else return a.y<b.y;
} int convex_hull(Point *p,int n,Point *tubao)
{
sort(p+1,p+n+1,cmp);
int m=0;
for(int i=1;i<=n;i++)
{
while(m>=2&&cross(p[i]-tubao[m-1],tubao[m]-tubao[m-1])>0) m--;
tubao[++m]=p[i];
}
int k=m;
for(int i=n-1;i>=1;i--)
{
while(m-k>=1&&cross(p[i]-tubao[m-1],tubao[m]-tubao[m-1])>0) m--;
tubao[++m]=p[i];
}
m--;
return m;
} int main()
{
int cas,n;
scanf("%d",&cas);
while(cas--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++) p[i].read();
int k=convex_hull(p,n,tubao);
tubao[k+1]=tubao[1]; bool flag=true;
double tmp=(n-2.0)*pi/n; for(int i=1;i<=k-1;i++)
{
Point a=tubao[i+1]-tubao[i],b=tubao[i+2]-tubao[i+1];
double cosang=dot(a,b)/(dis(a)*dis(b));
double ang=acos(cosang);
ang=pi-ang;
if(dcmp(ang-tmp)!=0) {flag=false;break;}
}
if(flag) printf("YES\n");
else printf("NO\n");
}
return 0;
}

  分析:主要是借助这道题来分下下计算几何的精度问题,

double型数据精度处理的两种方式

1.相除改为ong long相乘,这种是肯定对的,不会错。

2.dcmp函数,这种比较简单,但是有一定的精度条件,如果角度是1/999999-1/1000000,那么相减起来就是1e-6*1/999999为1e-12级别,这样是可以使用dcmp的,比如本道题,因为1-e4<=x<=1e4,那么最小的角度差是1/(2*1e4-1)-1/2*1e4(最小的角是1/2*1e4,第二小的角度是1/(2*1e4-1))为1e-8级别>1e-12级别,所以可以用dcmp(eps<1e-12)

 

最新文章

  1. android:configChanges=&quot;keyboard|keyboardHidden|orientation|screenSize&quot;
  2. SQL 2014 AlwaysOn 搭建
  3. 读 [The Root of Lisp]
  4. 如何清除SQL Server Management Studio的最近服务器列表
  5. 统计在从1到n的正整数中1出现的次数
  6. Xcode快捷键大全
  7. POJ3694 Network
  8. Android 应用开发耗电量控制。。
  9. MEF 编程指南(十二):批量组合
  10. 移动web:tab选项卡
  11. 高效PHP程序必知的53个技巧
  12. 认识 Java Message Service
  13. GDAL——命令使用专题——gdalsrsinfo命令
  14. 支持MPI的hdf5库的编译
  15. 【合集】Hadoop 合集
  16. SSH, 整合分页功能,连带DAO经典封装
  17. PAT甲级1052 Linked List Sorting
  18. AC自动机算法学习
  19. 如何优雅的退出/关闭/重启gunicorn进程
  20. Excel中用countif和countifs统计符合条件的个数 good

热门文章

  1. C++ 包含目录、库目录、附加包含目录、附加库目录、附加依赖项之详解(转)
  2. 从入门到自闭之Python--RESTful API规范与序列化
  3. 【python tkinter】对于窗口存在的认识
  4. Css文字效果
  5. 如何从git上批量拉取本地当前分支的所有代码
  6. 1.移动端自动化测试-知识笔记(面试必备,测试点,adb命令)
  7. Windows去除开始菜单图标背景
  8. kubernetes资源清单之DaemonSet
  9. 04-【servlet转发和重定向】
  10. ORACLE 常用函数学习笔记