HDU 5533(计算几何+暴力)

布满荆棘的人生 2022-06-08 10:51 206阅读 0赞

问题描述:

The sky was brushed clean by the wind and the stars were cold in a black sky. What a wonderful night. You observed that, sometimes the stars can form a regular polygon in the sky if we connect them properly. You want to record these moments by your smart camera. Of course, you cannot stay awake all night for capturing. So you decide to write a program running on the smart camera to check whether the stars can form a regular polygon and capture these moments automatically.   
  
Formally, a regular polygon is a convex polygon whose angles are all equal and all its sides have the same length. The area of a regular polygon must be nonzero. We say the stars can form a regular polygon if they are exactly the vertices of some regular polygon. To simplify the problem, we project the sky to a two-dimensional plane here, and you just need to check whether the stars can form a regular polygon in this plane.

Input

The first line contains a integer TT indicating the total number of test cases. Each test case begins with an integer nn, denoting the number of stars in the sky. Following nn lines, each contains 22 integers xi,yixi,yi, describe the coordinates of nnstars.   
  
1≤T≤3001≤T≤300   
3≤n≤1003≤n≤100   
−10000≤xi,yi≤10000−10000≤xi,yi≤10000   
All coordinates are distinct.

Output

For each test case, please output "\`YES\`" if the stars can form a regular polygon. Otherwise, output "\`NO\`" (both without quotes).

Sample Input

3
    3
    0 0
    1 1
    1 0
    4
    0 0
    0 1
    1 0
    1 1
    5
    0 0
    0 1
    0 2
    2 2
    2 0

Sample Output

NO
    YES
    NO

题目题意:题目给我们n个点，问这n点能否构成一个正n变形。

题目分析:我们暴力去找这个n个点之间最短的距离(这是边长)，然后去暴力遍历每个点能否找到与其他点之间的距离为最短距离，每个点都有，注意重复。通过画图我发现，如果找到一条边等于最短距离，我们把它的俩个端点的标记++，那么它是正多形，最后它的每个点的标记为4.

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #define ll long long
    using namespace std;
    
    const int maxn=105;
    struct note
    {
        ll x,y;
    }point[maxn];
    int vis[maxn];
    ll get_dis(int a,int b)//距离的平方，不影响
    {
        return (point[a].x-point[b].x)*(point[a].x-point[b].x)+(point[a].y-point[b].y)*(point[a].y-point[b].y);
    }
    int n;
    bool check()
    {
        for (int i=1;i<=n;i++) {
            if (vis[i]!=4)//不为4肯定不是
            return false;
        }
        return true;
    }
    int main()
    {
        int t;
        scanf("%d",&t);
        while (t--) {
            scanf("%d",&n);
            memset (point,0,sizeof (point));
            for (int i=1;i<=n;i++)
                scanf("%lld%lld",&point[i].x,&point[i].y);
            ll minlen=100000000000;
            for (int i=1;i<=n;i++) {
                for (int j=1;j<=n;j++) {
                    if (i==j) continue;
                    ll len=get_dis(i,j);
                    minlen=min(minlen,len);
                }
            }
            ll ans=0;
            memset(vis,0,sizeof (vis));
            for (int i=1;i<=n;i++) {
                for (int j=1;j<=n;j++) {
                    if (i==j) continue;
                    if (get_dis(i,j)==minlen) {
                           vis[i]++;
                           vis[j]++;
                    }
                }
            }
            if (check())
                printf("YES\n");
            else
                printf("NO\n");
        }
        return 0;
    }