AtCoder AGC #021 : B - Holes

これはまぁなんとか。
https://agc021.contest.atcoder.jp/tasks/agc021_b

問題

とても広い平面にいくつかの点がある。
平面上の各領域を、最寄りの点で分類したとき、それぞれの点に分類される領域の面積比を求めよ。

解法

厳密に解くにはボロノイ図を求めなければいけないが、今回無限に広い平面を考えることを考えると、対象の点の周辺は誤差の範囲で、その外側の領域をどれだけ占められるかが重要となる。
各頂点vに分類される領域の集合は、厳密には他の頂点wとの間で垂直二等分線を引き、v側を取る、ということを全頂点wに大して行いその積集合を取ったものとなる。
ここで、無限遠の領域をどれだけ確保できるか、と考えると垂直二等分線を少しずらし頂点vに重ねてみよう。
そうすると頂点vに分類される領域の面積は、180度の領域の積集合として得られる角度と比例することがわかる。
そう考えると、結局この問題は面積ではなく角度の問題に置き換えることができる。

積集合を取る各領域は幅が180度固定なので、割と手抜きで判定できる。

int N;
ll X[101],Y[101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	double pi=atan(1)*4;
	
	cin>>N;
	FOR(i,N) cin>>X[i]>>Y[i];
	FOR(i,N) {
		double L=-1010,R=0;
		vector<double> D;
		FOR(j,N) if(i!=j) {
			ll dx=X[j]-X[i];
			ll dy=Y[j]-Y[i];
			D.push_back(atan2(dx,dy));
		}
		
		sort(ALL(D));
		D.push_back(D[0]+2*pi);
		double ret=0;
		FOR(j,D.size()-1) {
			if(D[j+1]-D[j]>=pi) ret=(D[j+1]-D[j])-pi;
		}
		
		_P("%.12lf\n",ret/(2*pi));
	}
	
}

まとめ

これは600ptぐらいかな。