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

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

[题目链接][Link 1]

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

转载于:https://www.cnblogs.com/Just--Do--It/p/7246451.html

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=6055