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とする。余弦定理よりである。
ここからθが求まる。
あとは扇形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); }
まとめ
解き方自体はすんなり思いついたのだけど、また誤差ゲーで落とされた…。