kmjp's blog

競技プログラミング参加記です

Codeforces ECR #002 : D. Area of Two Circles' Intersection

ECR#1に続いてまたも誤差ゲー。
http://codeforces.com/contest/600/problem/D

問題

2次元座標中で2つの円が与えられる。
両者の共通部分の面積を求めよ。

解法

片方が片方を完全に含むとき、あと双方共通部分がないときの解は明確。
両者の円周が交差する場合を考える。
2つの円の中心をA,B、円周の交点をC,Dとする。
円の半径をS,T、2つの円の中心の距離をLとする。

求める面積は、扇形ACDから三角形ACDの面積を引いたものと、扇形BCDから三角形BCDの面積を引いたものを足したものである。
以下前者について考える。
θ=∠CABとする。余弦定理より S^2 + L^2 - 2SL\cos \theta = T^2である。
ここからθが求まる。
あとは扇形ACDの面積は2θS^2、三角形ACDの面積はS^2*cos(θ)*sin(θ)である。
扇形BCD・三角形BCDの面積も同様に求められる。

登場する整数が大きいので、long doubleを使った方が無難。

ll X[2],Y[2],R[2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	long double PI=atan(1)*4;
	
	FOR(i,2) cin>>X[i]>>Y[i]>>R[i];
	
	if(R[0]<R[1]) swap(X[0],X[1]),swap(Y[0],Y[1]),swap(R[0],R[1]);
	X[1]-=X[0];
	Y[1]-=Y[0];
	if(X[1]*X[1]+Y[1]*Y[1]>=(R[0]+R[1])*(R[0]+R[1])) return _P("0\n");
	if(sqrt(X[1]*X[1]+Y[1]*Y[1])+R[1]<=R[0]) return _P("%.12lf\n",(double)(PI*R[1]*R[1]));
	long double A=R[0];
	long double B=R[1];
	long double D=sqrt(X[1]*X[1]+Y[1]*Y[1]);
	long double S=0;
	FOR(i,2) {
		long double co=(A*A+D*D-B*B)/(2*A*D);
		long double the=acos(co);
		S+=the*A*A;
		S-=A*sin(the)*A*cos(the);
		swap(A,B);
	}
	_P("%.12lf\n",(double)S);
	
}

まとめ

解き方自体はすんなり思いついたのだけど、また誤差ゲーで落とされた…。