2017ACM暑期多校联合训练 - Team 2 1011 HDU 6055 Regular polygon （数学规律）

题目链接

**Problem Description

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

题意：

给出一系列得坐标点，看这些点能够构成得正多边形有多少个，虽然题目中问的是正多边形，但是我们需要考虑到一点就是题目中说给出的坐标点都是整数，呢么就可以确定仅可以构成正四边形，我们只需要找其中的正四边形得个数就行了。

分析：

为了解决同一个图形通过不同的点重复查找到的情况，我们把这些点的坐标先按照横坐标从小到大，再按照纵坐标从小打到排序，然后我们从小到大取两个点确定一条线，在确定这条线对应的正方形。

#include <bits/stdc++.h>

using namespace std;

const int maxn=510;

struct Node///先按横坐标从大到小，再按纵坐标从大到小

{

    int x,y;

    bool operator<(const Node& rhs)const

    {

        if(x == rhs.x)

            return y < rhs.y;

        else

            return x < rhs.x;

    }

} nodes[maxn];

int main()

{

    int n;

    while(scanf("%d",&n)==1 && n)

    {

        int ans=0;///正方形个数

        for(int i=0; i<n; ++i)

            scanf("%d%d",&nodes[i].x,&nodes[i].y);

        sort(nodes,nodes+n);

        //for(int i=0; i<n; ++i)

          //  printf("%d    %d\n",nodes[i].x,nodes[i].y);

        for(int i=0; i<n; ++i)

            for(int j=i+1; j<n; ++j)

            {

                ///看一下以i，j两个点作为正方形得一条边能不能找到其余的两个顶点

                Node tmp;//tmp作为正方形的第3或4个点

                tmp.x=nodes[i].x+nodes[i].y-nodes[j].y;

                tmp.y=nodes[i].y+nodes[j].x-nodes[i].x;

                if(!binary_search(nodes,nodes+n,tmp)) continue;

                tmp.x=nodes[j].x+nodes[i].y-nodes[j].y;

                tmp.y=nodes[j].y+nodes[j].x-nodes[i].x;

                if(!binary_search(nodes,nodes+n,tmp)) continue;

                ///只有两个点都找到才能够构成一个正方形

                ++ans;

            }

        printf("%d\n",ans/2);///注意这里/2，原因是因为一个正方形可以通过最最左下角得那个点向上和向右分别找到同一个正方形两次

    }

    return 0;

}

巴特西

2017ACM暑期多校联合训练 - Team 2 1011 HDU 6055 Regular polygon （数学规律）

最新文章

热门文章