Educational Codeforces Round 1 C. Ancient Berland Circus

問題

三点の座標が与えられて，三点で構築できる最小の正多辺形の面積を求めなさい

解法

• 与えられた三点からなった三角形の三つの内角の角度のGCD（最大公約数）を求める．それは構成できる正多辺形の一つの辺が360度に対応する角度である．なので，これで構成できる最小の辺の数を持つ正多辺形の辺の数を求めることができる．

• 三角形の外接円の半径を求める．

• 角度と半径と辺の数で正多辺形の面積を求める．

分類

幾何，三角形

コード

#include <bits/stdc++.h>
using namespace std;
 
const double PI = acos(-1);
using ll = long long;
using ull = unsigned long long;
const int inf = 2e9;
const ll INF = 4e18;
const ll MOD = 1e9+7;
const double eps = 1;
typedef pair<int,int> P;
 
template <typename T>
class Triangle{
public:
  T xa, xb, xc, ya, yb, yc;
  T S, R;
  T a, b, c;
  T Ap, Bp, Cp;
 
  Triangle(T x1, T y1, T x2, T y2, T x3, T y3) {
    xa = x1; xb = x2; xc = x3;
    ya = y1; yb = y2; yc = y3;
 
    a = sqrt((xb-xc)*(xb-xc)+(yb-yc)*(yb-yc));
    b = sqrt((xa-xc)*(xa-xc)+(ya-yc)*(ya-yc));
    c = sqrt((xb-xa)*(xb-xa)+(yb-ya)*(yb-ya));
 
    S = abs((x2-x1)*(y3-y1) - (x3-x1)*(y2-y1))/2;
    R = a*b*c/(4*S);
 
    Ap = acos((b*b+c*c-a*a)/(2*b*c));
    Bp = acos((a*a+c*c-b*b)/(2*a*c));
    Cp = acos((b*b+a*a-c*c)/(2*b*a));
  }
};
 
double toAngle(double angle) {
  return 180 * angle / PI;
}
 
double toPI(double angle) {
  return PI * angle / 180;
}
 
double gcd(double x, double y) {
  while (abs(x) > eps && abs(y) > eps) {
    if (x > y) {
      x -= floor(x/y) * y;
    } else {
      y -= floor(y/x) * x;
    }
  }
  return x + y;
}
 
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
 
  double x1,y1,x2,y2,x3,y3;
  cin>>x1>>y1>>x2>>y2>>x3>>y3;
 
  Triangle<double> t(x1,y1,x2,y2,x3,y3);
 
  double n = gcd(gcd(toAngle(t.Ap), toAngle(t.Bp)), toAngle(t.Cp));
  n = 180 / n;
  cout << setprecision(20) << n * t.R * t.R * sin(2 * PI / n) / 2 << endl;
  return 0;
}