数学题(正多边形判定)HDU 5533-Dancing Stars on Me

桃扇骨 2022-05-15 04:58 180阅读 0赞

*  # **数学题(正多边形判定)HDU 5533-Dancing Stars on Me** #

--------------------

*  ## 题目链接： ##

### [Dancing Stars on Me][] ###

*  ## 思路： ##

### 题目大意： ###

给n个点坐标，判断是否能构成正多边形

### 题解： ###

**对于正多边形，某点与它左右相邻的两个点的距离相等且最小，不能满足该条件，则不能构成**

**对每个点，这个最小距离应相等，不符合则不能构成**

按以上两个条件写代码就能AC，一脸懵逼我也不知道为什么数据这么少

个人觉得还得再加一个条件：

***每个点同另外两个点构成的角有最大值，必须满足两个点分别左右相邻！！！***

懒，不改了

*  ## 代码： ##

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    #include<set>
    using namespace std;
    #define MAX_SIZE 105
    
    struct Point
    {
        int x;
        int y;
    };
    Point Point_List[MAX_SIZE];
    int main()
    {
        int T,n;
        cin>>T;
        while(T--)
        {
            int flag=0;
            set<double> Check_Again;
            cin>>n;
            for(int i=1;i<=n;i++)
                scanf("%d%d",&Point_List[i].x,&Point_List[i].y);
            for(int i=1;i<=n;i++)
            {
                double MIN=1e9;
                int Cnt=0;
                for(int j=1;j<=n;j++)
                {
                    double Dis=sqrt(pow(Point_List[i].x-Point_List[j].x,2)+pow(Point_List[i].y-Point_List[j].y,2));   
                    if(Dis==0)
                        continue;
                    if(Dis==MIN)
                        Cnt++;
                    MIN=min(Dis,MIN);
                }
                if(Cnt!=1)   //不等于1，说明最小值多与2
                {
                    flag=1;
                    break;
                }
                Check_Again.insert(MIN);   //用set去重
                if(Check_Again.size()>1)   //set中存的是每个点的最小值，如果点之间最小值不相等，也是错的
                {
                    flag=1;
                    break;
                }
            }
            if(flag)
                cout<<"NO"<<endl;
            else
                cout<<"YES"<<endl;
        }
        return 0;
    }

[Dancing Stars on Me]: http://acm.hdu.edu.cn/showproblem.php?pid=5533