Regular polygon

﹏ヽ暗。殇╰゛Y 2022-06-10 14:28 153阅读 0赞

On a two-dimensional plane, give you n integer points. Your task is to figure out how many different regular polygon these points can make.

Input

The input file consists of several test cases. Each case the first line is a numbers N (N <= 500). The next N lines ,each line contain two number Xi and Yi(-100 <= xi,yi <= 100), means the points’ position.(the data assures no two points share the same position.)

Output

For each case, output a number means how many different regular polygon these points can make.

Sample Input

4
    0 0
    0 1
    1 0
    1 1
    6
    0 0
    0 1
    1 0
    1 1
    2 0
    2 1

Sample Output

1
     2 以相邻的顶点为基准来计算未知顶点进行判断
    由两个点便可以得到可能满足正方形情况的两个点，判断这两个点是否存在就好了，注意在计算的过程中每个正方形有四条边所以会被统计四遍，最终结果应是 ans/4。
     #include <iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    int x[507],y[507];
    int visit[207][207];
    int main()
    {
        int n,ans;
        while(~scanf("%d",&n))
        {
            ans=0;
            memset(visit,0,sizeof(visit));
            for(int i=0;i<n;i++)
            {
                scanf("%d %d",&x[i],&y[i]);
                x[i]+=100,y[i]+=100;
                visit[x[i]][y[i]]=1;
            }
            for(int i=0;i<n;i++)
            {
                for(int j=i+1;j<n;j++)
                {
                    int dx=x[j]-x[i];
                    int dy=y[j]-y[i];                 //找出正方形的另外两个点,并判断是否存在                 if(x[i]+dy>=0&&x[i]+dy<=200&&y[i]-dx>=0&&y[i]-dx<=200&&x[j]+dy>=0&&x[j]+dy<=200&&y[j]-dx>=0&&y[j]-dx<=200&&visit[x[i]+dy][y[i]-dx]&&visit[x[j]+dy][y[j]-dx])
                        ans++;
                    if(x[i]-dy>=0&&x[i]-dy<=200&&y[i]+dx>=0&&y[i]+dx<=200&&x[j]-dy>=0&&x[j]-dy<=200&&y[j]+dx>=0&&y[j]+dx<=200&&visit[x[i]-dy][y[i]+dx]&&visit[x[j]-dy][y[j]+dx])
                        ans++;
                }
            }
            printf("%d\n",ans/4);
        }
        return 0;
    }
    
    从对角线的两个点找另外两个点

#include <iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    int x[507],y[507];
    int visit[607][607];
    int main()
    {
        int n,ans;
        while(~scanf("%d",&n))
        {
            ans=0;
            memset(visit,0,sizeof(visit));
            for(int i=0;i<n;i++)
            {
                scanf("%d %d",&x[i],&y[i]);
                x[i]+=100,y[i]+=200;
                visit[x[i]][y[i]]=1;
            }
            for(int i=0;i<n;i++)
            {
                for(int j=i+1;j<n;j++)
                {
                    double xa=(x[i]+x[j])/2.0;
                    double ya=(y[i]+y[j])/2.0;
                    double xb=xa-x[i];
                    double yb=ya-y[i];
                    //因为比如(2,3)和(4,2)这样的两个点是不存在正方形的;
                    if((int)(xa+yb)!=xa+yb||(int)(ya-xb)!=ya-xb||(int)(xa-yb)!=xa-yb||(int)(ya+xb)!=ya+xb)
                        continue;
                    if((int)(xa+yb)>=0&&(int)(ya-xb)>=0&&(int)(xa-yb)>=0&&(int)(ya+xb)>=0&&visit[(int)(xa+yb)][(int)(ya-xb)]&&visit[(int)(xa-yb)][(int)(ya+xb)])
                    {
                        ans++;
                    }
                }
            }
            printf("%d\n",ans/2);
        }
        return 0;
    }