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

布满荆棘的人生 2023-06-01 11:15 10阅读 0赞

题目链接：[https://codeforces.com/problemset/problem/1/C][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 }

转载于:https://www.cnblogs.com/Carered/p/11545746.html

[https_codeforces.com_problemset_problem_1_C]: https://codeforces.com/problemset/problem/1/C