MYF

HDU 5563 Clarke and five-pointed star

Posted on | In | | Visitors

题目链接

HDU 5563

BestCoder #62B

方法：正五角星的判断

题目分析

题目大意

t组数据，每组数据五行，分别代表每个点的x,y，问，这五个点能否构成正五角星。

解析

先看看作者的解析：

容易看出只需要判断这5个点是否在一个正五边形上。

因此我们枚举排列，然后依次判断即可。

判定方法是，五条相邻边相等，五条对角线相等。

当然题目给的精度问题，窝只能说，如果泥做法不复杂，精度足够好的话，是可以过的。毕竟题目说的小于

10－4
是指理论上的，所以理论上适用所有的数之间的比较。所以有人问我开方前和开方后，我只能说，哪个精度高用哪个….
当然你也可以先求出凸包然后再判相邻距离……

拿到题，一直以为是判定凸包，到最后可以hack的时候才发现是判定正五角星，一下难度降低了不止一个档次，赛后看完题解，五分钟敲出来了。
如果不看题解的话，自己还是会选择用黄金分割比来计算，看过题目作者的思路之后，还是觉得用五条相邻边相等，五个对角线(即构成五角星的五条线)相等的方法更简单一些。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <stack>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define PI acos(-1)
#define debug         printf("Hi----------\n")
#define eps 1e-4
#define INF 0x3f3f3f3f
#pragma comment(linker, "/st:1024000000,1024000000")
typedef long long ll;
using namespace std;
#define MAXN 10
int mp[5][5];
struct point{
    double x,y;
}p[5];
double dis(point p1,point p2){  //计算 p1p2的 距离
    return sqrt((p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y));
}
double max(double a,double b){
    if (a>b)
        return a;
    else
        return b;
}
int main()
{
    int t,index;
    double mx;
    double vis[10];
    bool flag;
    scanf("%d",&t);
    while (t--) {
        mx=0;
        index=0;
        flag=true;
        for (int i=0; i<5; i++) {
            scanf("%lf%lf",&p[i].x,&p[i].y);
        }
        
        //记录五边形的五条边、五角星的五个对角线
        for (int i=0; i<5; i++) {
            for (int j=i+1; j<5; j++) {
                vis[index++]=dis(p[i],p[j]);
            }
        }
        
        sort(vis, vis+10);
        
        //判断五条相邻边是否相等
        for (int i=1; i<5; i++) {
            if (fabs(vis[i]-vis[i-1])>eps) {
                flag=false;
            }
        }
        
        //判断五条对角线是否相等
        for (int i=6; i<10; i++) {
            if (fabs(vis[i]-vis[i-1])>eps) {
                flag=false;
            }
        }
        
        //Output
        if (flag)
            printf("Yes\n");
        else
            printf("No\n");
        
    }
    return 0;
}