hdu 6055 : Regular polygon (2017 多校第二场 1011）【计算几何】-蒲公英云

hdu 6055 : Regular polygon (2017 多校第二场 1011）【计算几何】

红太狼 2021-12-16 09:35 320阅读 0赞

题目链接

有个结论：平面坐标系上，坐标为整数的情况下，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);
    }
}