首页 > 代码库 > hdu_6055 : Regular polygon (2017 多校第二场 1011) 【计算几何】
hdu_6055 : Regular polygon (2017 多校第二场 1011) 【计算几何】
题目链接
有个结论: 平面坐标系上,坐标为整数的情况下,n个点组成正n边形时,只可能组成正方形。
然后根据这个结论来做。
我是先把所有点按照 x为第一关键字,y为第二关键字 排序,然后枚举向量 (p[i]->p[j]) (j>i),只判断这个向量左侧可否存在两个点与它一起构成一个正方形。这样算的结果是,计数每个正方形时,它的靠右和靠下的两条边都会为ans贡献一个单位,所以最后ans要除以2。
#include<bits/stdc++.h> using namespace std; int n; int vis[605][605]; struct point { int x,y; bool operator<(const point& rhs)const { return x<rhs.x || x==rhs.x&&y<rhs.y; } }p[505]; int main() { while(~scanf("%d",&n)) { memset(vis,0,sizeof(vis)); int ans=0; for(int i=0;i<n;i++) { scanf("%d%d",&p[i].x,&p[i].y); p[i].x+=300,p[i].y+=300; vis[p[i].x][p[i].y]=1; } sort(p,p+n); for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) { point a=p[i],b=p[j]; int dx=b.x-a.x; int dy=b.y-a.y; point c,d; c.x=a.x-dy,c.y=a.y+dx; d.x=b.x-dy,d.y=b.y+dx; if(vis[c.x][c.y]&&vis[d.x][d.y]) ans++; } printf("%d\n",ans/2); } }
hdu_6055 : Regular polygon (2017 多校第二场 1011) 【计算几何】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。