[CF1C] Ancient Berland Circus

[CF1C] Ancient Berland Circus

Description

一个规则 (等角) 多边形，得到了这三根柱子的坐标，输出古代竞技场的可能的最小区域面积。

Solution

始终围绕着该多边形的外接圆来做，假设三个顶点 A,B,C 对应的圆周角为 A,B,C，对应的对边长度为 a,b,c。

用海伦公式求出三角形面积 S，用正弦定理求出外接圆半径 R，用余弦定理求出各边对应的圆周角 oa,ob,oc（其实只需要求其中两个），然后求最大公约数得到正多边形每边对应的圆心角 theta，进而得到整个图形的面积 ans。

精度很玄学……

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1000005;

signed main()
{
    // freopen("D:\XCPCWorkspace\cf\contest\1\c\in1.txt","r",stdin);
    double ax, ay, bx, by, cx, cy;

    cin >> ax >> ay >> bx >> by >> cx >> cy;
    double a = sqrt(pow(cx - bx, 2) + pow(cy - by, 2));
    double b = sqrt(pow(ax - cx, 2) + pow(ay - cy, 2));
    double c = sqrt(pow(ax - bx, 2) + pow(ay - by, 2));

    double a2 = pow(cx - bx, 2) + pow(cy - by, 2);
    double b2 = pow(ax - cx, 2) + pow(ay - cy, 2);
    double c2 = pow(ax - bx, 2) + pow(ay - by, 2);

    double s2 = (a + b + c) / 2 * ((a + b + c) / 2 - a) * ((a + b + c) / 2 - b) * ((a + b + c) / 2 - c);

    // double r = a * b * c / 4 / s;
    double r2 = a2 * b2 * c2 / s2 / 16;

    double oa = acos(1 - a2 / 2 / r2 + 1e-13);
    double ob = acos(1 - b2 / 2 / r2 + 1e-13);

    if (oa < 0 || ob < 0)
        puts("negative"),
            throw("negative");

    int cnt = 0;

    function<double(double, double)> fgcd = [&](double a, double b) -> double {
        ++cnt;
        if (cnt > 10000)
            puts("stack overflow"), cout << a << " " << b << endl,
                throw("stack overflow");
        if (b < 1e-4)
            return a;
        if (a < 1e-4)
            return b;
        return fgcd(b, fmod(a, b));
    };

    double og = fgcd(fgcd(2 * acos(-1), oa), fgcd(2 * acos(-1), ob));

    double n = round(2 * acos(-1) / og);
    og = 2 * acos(-1) / n;
    double ans = n * 0.5 * sin(og) * r2;

    cout << setiosflags(ios::fixed) << setprecision(10) << ans << endl;
}