Codeforces Round #1 C - Ancient Berland Circus：幾何求正多邊形面積

問題描述

給定三角形三頂點坐標，這三點是某正多邊形的三個頂點。求該正多邊形的最小可能面積。

解題步驟

1. 求外接圓半徑 R：由三角形三邊長 a,b,c 和面積 S，公式 R = a*b*c / (4*S)。S 用海倫公式。
   
2. 求三個中心角：對應邊長 a 的中心角 α = 2 * arcsin(a / (2R))，或用餘弦定理 α = acos(1 - a²/(2R²))。三角和為 2π。
   
3. 求中心角的最大公約數：正多邊形的中心角為 2π/n。三個給定中心角必須是基本中心角的整數倍。故基本中心角 = gcd(α, β, γ)。對浮點數用 fmod 模擬輾轉相除。
   
4. 計算面積：n = 2π / 基本中心角。正 n 邊形面積 S = n * R² * sin(2π/n) / 2 = R² * π * sin(θ) / θ，其中 θ = 基本中心角。
   

代碼實現 (C++)

#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1.0);
struct Pt { double x, y; };
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
double fgcd(double a, double b) {
    if (fabs(a) < 1e-9) return b;
    if (fabs(b) < 1e-9) return a;
    return fgcd(b, fmod(a, b));
}
int main() {
    Pt p[3];
    for (int i = 0; i < 3; ++i) cin >> p[i].x >> p[i].y;
    double a = dist(p[0], p[1]);
    double b = dist(p[1], p[2]);
    double c = dist(p[2], p[0]);
    double s = (a + b + c) / 2;
    double area = sqrt(s * (s - a) * (s - b) * (s - c));
    double R = a * b * c / (4 * area);
    double ang[3];
    ang[0] = acos(1 - a * a / (2 * R * R));
    ang[1] = acos(1 - b * b / (2 * R * R));
    ang[2] = 2 * PI - ang[0] - ang[1];
    double g = fgcd(ang[0], ang[1]);
    g = fgcd(g, ang[2]);
    double ans = R * R * PI * sin(g) / g;
    printf("%.6f\n", ans);
    return 0;
}

關鍵細節

• 浮點數 GCD 需設容差（如 1e-9），避免無限遞歸。
• 中心角計算用 acos 避免 arcsin 精度問題。
• 最終面積公式推導：S = n * R² * sin(2π/n) / 2，代入 n = 2π/g 化簡得 R² * π * sin(g) / g。

複雜度

• 時間：O(1)，僅涉及常數次三角函數運算。
• 空間：O(1)。

這題將幾何性質（正多邊形頂點在同一圓上，中心角為基本角整數倍）轉化為浮點數 GCD 問題，是計算幾何與數論結合的經典例題。