UVa 10439 - Temple of Dune

链接

传送门

题意

给出三个点, 问这三个点最少是正几边形的顶点。

思路

之前组队赛做过,三个点在正多边形的外接圆,三个点的两两关于圆心的夹角是正多边形相邻两点圆心角的倍数,枚举正多边形的边数依次检验即可。

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const double eps = 1e-5;
const double PI2 = acos(-1) * 2;
const int maxn = 5;
const int maxm = 1010;
double ANG[maxm];
struct Point {
double x, y;
Point() {}
Point(double x, double y) : x(x), y(y) {}
} p[maxn];
typedef Point Vector;
Vector operator - (Vector a, Vector b) {
return Vector(a.x - b.x, a.y - b.y);
}
int dcmp(double x) {
if (fabs(x) < eps) {
return 0;
}
return x > 0 ? 1 : -1;
}
double Dot(const Vector& A, const Vector& B) {
return A.x * B.x + A.y * B.y;
}
double Length(const Vector& A) {
return sqrt(Dot(A, A));
}
double Angle(const Vector& A, const Vector& B) {
return acos(Dot(A, B) / Length(A) / Length(B));
}
bool check(double a, double mod) {
a -= floor(a / mod) * mod;
return dcmp(a) == 0 || dcmp(a - mod) == 0;
}
int main() {
for (int i = 3; i < maxm; ++i) {
ANG[i] = PI2 / i;
}
int t;
scanf("%d", &t);
while (t--) {
for (int i = 0; i < 3; ++i) {
scanf("%lf%lf", &p[i].x, &p[i].y);
}
double ang1 = 2 * Angle(p[0] - p[2], p[1] - p[2]);
double ang2 = 2 * Angle(p[1] - p[0], p[2] - p[0]);
double ang3 = 2 * Angle(p[2] - p[1], p[0] - p[1]);
int ans = 0;
for (int i = 3; i < maxm; ++i) {
if (check(ang1, ANG[i]) && check(ang2, ANG[i]) && check(ang3, ANG[i])) {
ans = i;
break;
}
}
printf("%d\n", ans);
}
return 0;
}

支付宝扫码领红包