盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 更新日志

CF 1C Ancient Berland Circus (几何)

题目

源地址:http://codeforces.com/problemset/problem/1/C

题意

有一个正多边形(3<=n<=100),现在只知道其中的三个顶点,问这个正多边形最小可能的面积。

思路

首先可以知道,这个正多边形一定是有一个外接圆的。可以通过给定的三个点,构造三角形,然后求得外接圆。
外接圆的求法:
用余弦定理得到角A,然后用正弦定理得到 a / sinA = 2 * R
之后可以得到每条边对应的圆心角。这三个圆心角一定是正多边形每条边对应圆心角的整数倍。由于n范围很小,才100。只要枚举一下n,找到最小的答案即可。
我看网上还有种做法:三个圆心角A,B,C。那么正多边形每条边对应圆心角 = gcd(A, B, C) = gcd(gcd(A, B), C)
这里用到了辗转相减法来求double的gcd,机智的做法(这就可以解决n很大的问题了)

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
/*
ID: wuqi9395@126.com
PROG:
LANG: C++
*/
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<fstream>
#include<cstring>
#include<ctype.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF (1 << 30)
#define LINF (1LL << 60)
#define PI acos(-1.0)
#define mem(a, b) memset(a, b, sizeof(a))
#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, a, n) for (int i = n - 1; i >= a; i--)
#define eps 1e-6
#define debug puts("===============")
#define pb push_back
#define mkp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define POSIN(x,y) (0 <= (x) && (x) < n && 0 <= (y) && (y) < m)
typedef long long ll;
typedef unsigned long long ULL;
double px[3], py[3];
double a, b, c;
double A, B, C;
double dis(int i, int j) {
double x = px[i] - px[j], y = py[i] - py[j];
return sqrt(x * x + y * y);
}
double get(double a, double b, double c) {
return acos((b * b + c * c - a * a) / (2 * b * c));
}
bool check(int n) {
double e = 2 * PI / n;
//cout<<e<<"---------";
int x = (A + eps) / e, y = (B + eps) / e, z = (C + eps) / e;
//cout<<n<<" "<<x<<" "<<y<<" "<<z<<" "<<endl;
if (fabs((x + y + z) * e - 2 * PI) < 1e-6) return true;
return false;
}
double cal(int n, double R) {
double ans = R * R * sin(2 * PI / n) / 2 * n;
return ans;
}
int main () {
for (int i = 0; i < 3; i++) scanf("%lf%lf", &px[i], &py[i]);
a = dis(0, 1);
b = dis(1, 2);
c = dis(2, 0);
//cout<<a<<" "<<b<<" "<<c<<" "<<endl;
//余弦定理得到三角形的角度
A = get(a, b, c);
B = get(b, a, c);
C = get(c, a, b);
double R = a / sin(A) / 2;
//转化为圆心角
A *= 2, B *= 2, C *= 2;
//cout<<A<<" "<<B<<" "<<C<<" "<<R<<endl;
int n;
for (n = 3; n <= 100; n++) {
if (check(n)) break;
}
//cout<<n<<endl;
printf("%.10lf\n", cal(n, R));
return 0;
}

更新日志

  • 2014-11-2 AC