C. Ancient Berland Circus（三点确定最小多边形）-蒲公英云

C. Ancient Berland Circus（三点确定最小多边形）

题目链接：https://codeforces.com/problemset/problem/1/C

题意：对于一个正多边形，只给出了其中三点的坐标，求这个多边形可能的最小面积，给出的三个点一定能够组成三角形。

思路：根据三角形三个顶点的坐标求得三角形的三边长a、b、c，海伦公式和正弦定理连理得半径R = abc / (4S)，再求出外接圆圆心到三角形三个顶点组成的三个圆心角∠1、∠2、∠3的最大公约数作为正多边形的每一份三角形的内角，将所有三角形加起来即可。思路不难但是满满的细节orz，比如防止钝角的情况，边长最长的对应的圆心角应该这样求： 2*PI - 其他两个圆心角。

AC代码：

1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const double eps = 1e-4;
 4 const double pi = acos(-1.0);
 5 int sgn(double x)
 6 {
 7     if(fabs(x) < eps) return 0;
 8     else return x < 0 ? -1 : 1;
 9 }
10 double gcd(double a, double b)
11 {
12     if(sgn(b) == 0) return a;
13     if(sgn(a) == 0) return b;
14     return gcd(b, fmod(a,b));
15 }
16 struct Point{
17     double x, y;
18     void input(){
19         scanf("%lf%lf", &x, &y);
20     }
21     double distant(Point p)
22     {
23         double a = (x - p.x);
24         double b = (y - p.y);
25         return sqrt(a * a + b * b);
26     }
27 };
28 double angle(double a, double b, double c)
29 {
30     return acos((a * a + b * b - c * c)/(2.0 * a * b));
31 }
32 
33 int main()
34 {
35     Point point[3];
36     for(int i = 0;i < 3;i++) point[i].input();
37     double a = point[0].distant(point[1]);
38     double b = point[1].distant(point[2]);
39     double c = point[2].distant(point[0]);
40     if(a > c) swap(a, c);
41     if(b > c) swap(b, c);
42     double p = (a + b + c) / 2.0;
43     double S = sqrt(p*(p - a) * (p - b)* (p - c));
44     double r = (a * b * c) /(4.0 * S);
45     double A = angle(r, r, a);
46     double B = angle(r, r, b);
47     double C = 2 * pi - A - B;
48     double ave = gcd(A, gcd(B, C));
49     double ans = r * r * sin(ave)* pi / ave;
50     printf("%.8f\n",ans);
51     return 0;
52 }