Codeforces Beta Round #1 C. Ancient Berland Circus

問題ページ

Problem - C - Codeforces

問題文

　現在では、バーランドの円型競技場は、直径13mの円型アリーナを持っていますが、昔はそうではありませんでした。

　古代バーランドの円方競技場のアリーナの形は正多角形でした。その大きさと角度はそれぞれの闘技場によって異なりました。アリーナの全ての角には特別な柱がありました。ロープが柱同士を結んでアリーナの辺になっていました。

　最近、バーランドの科学者は古代の闘技場の形跡を発見しました。彼らは３本の柱のみを発見することができました。それ以外の柱は時間経過により破壊されていました。

　あなたはそれらの３本の柱の座標が与えられるので、そのアリーナが持っていたと考えられる最小の面積を出力してください。

制約

• 座標の絶対値は1000を超えない。

解法

↓反転

正多角形の頂点は外接円の円周にある。外接円の中心求めてあとはシミュレーション。

#include <iostream>
#include <cmath>
#include <cstdio>
#include <vector>
#include <complex>
using namespace std;
typedef complex<double > P;
const double EPS = 1e-5;
const double PI = asin(0.5) * 6;


P getCircumcenter(P a,P b,P c){
	double A1 = 2 * ( b.real() - a.real() );
	double B1 = 2 * ( b.imag() - a.imag() );
	double C1 = pow(a.real(),2)-pow(b.real(),2) + pow(a.imag(),2)-pow(b.imag(),2);
	double A2 = 2 * ( c.real() - a.real() );
	double B2 = 2 * ( c.imag() - a.imag() );
	double C2 = pow(a.real(),2)-pow(c.real(),2) + pow(a.imag(),2)-pow(c.imag(),2);
	double X = (B1 * C2 - B2 * C1) / (A1 * B2 - A2 * B1);
	double Y = (C1 * A2 - C2 * A1) / (A1 * B2 - A2 * B1);
	return P(X,Y);
}

 
double AreaOfPolygon(vector<P> p){
	double S = 0 ; 
	p.push_back(p[0]);
	for(int i = 0 ; i < p.size()-1 ; i++){
		S += (p[i].real() - p[i+1].real()) * (p[i].imag()+p[i+1].imag());
	}
	S /= 2.0;
	return S;
}

int same(P a,P b){
	return abs(a-b) < EPS;
}

int main(){
	int n;
	P a,b,c;
	cin >> a.real() >> a.imag() >> b.real() >> b.imag() >> c.real() >> c.imag();
	P g = getCircumcenter(a,b,c);
	a -= g;
	b -= g;
	c -= g;
	double R = abs(a);
	double f = atan2(a.imag(),a.real());
	for(int i = 3 ;  ; i++){
		double r = (2*PI) / i;
		int B = 0;
		vector<P> add;
		
		for(int j = 0 ; j < i ; j++){
			double t = f + (j * r);
			double x = R * cos(t) , y = R * sin(t);
			if(same(P(x,y),a)) B |= 1;
			else if(same(P(x,y),b)) B |= 2;
			else if(same(P(x,y),c)) B |= 4;
			add.push_back(P(x,y));
		}
		if(B==7){
			printf("%.10f\n",AreaOfPolygon(add));
			return 0;
		}
	}
}