Google Code Jam 2008 Qualification Round : C. Fly Swatter

予選最終問題。
http://code.google.com/codejam/contest/32013/dashboard#s=p2

ラケットとガットとボールの大きさが与えられるので、ボールを返せる確率を返す。
全体の面積がR*R*piなので、そこからガットの隙間の面積を返せばよい。
ガットで構成される１つの正方形の隙間の大きさは、ボールの半径を引いた(g-2r)*(g-2r)でよい。

問題はガットの隙間が外周にかかるとき。
これは丁寧に円弧とと多角形（三角形or台形or正方形の角を落とした形）の面積を求めると良い。

double f,R,t,r,g,PI,tr;

double segment(double nx,double ny) {
	double fx,fy,fx2,fy2,fx3;
	double deg;
	fx=nx+g-2*f;
	fy=ny+g-2*f;
	
	if(fx*fx+fy*fy <= tr*tr) return (g-2*f)*(g-2*f);
	
	//nxがnyより大きいので、円の周りは0～45度まで、よって
	//(nx,fy)が円の外で(fx,xy)が円の中になることはない
	
	//右上が円の外
	if(nx*nx+fy*fy<=tr*tr) { //左上が円の中
		if(fx*fx+ny*ny<=tr*tr) { //右下が円の中
			//上の欠けた点
			fx2 = sqrt(tr*tr-fy*fy);
			//右の欠けた点
			fy2 = sqrt(tr*tr-fx*fx);
			
			deg = atan2(fy,fx2)-atan2(fy2,fx);
			return deg*tr*tr/2 - (fy*fx-fy2*fx2)/2 + (fy-ny)*(fx-nx)-(fy-fy2)*(fx-fx2)/2;
		}
		else { //右下が円の外
			//上の欠けた点
			fx2 = sqrt(tr*tr-fy*fy);
			//下の欠けた点
			fx3 = sqrt(tr*tr-ny*ny);
			deg = atan2(fy,fx2)-atan2(ny,fx3);
			return deg*tr*tr/2 - (fy*fx3-ny*fx2)/2 + (fy-ny)*(fx2+fx3-2*nx)/2;
		}
	}
	
	//左上も右下も円の外
	fy = sqrt(tr*tr-nx*nx);
	fx = sqrt(tr*tr-ny*ny);
	deg = atan2(fy,nx)-atan2(ny,fx);
	return deg*tr*tr/2 - (fy*fx-ny*nx)/2 + (fy-ny)*(fx-nx)/2;
}

void solve(int _loop) {
	int i,j,k,m,result;
	double ta,ha,re;
	
	PI=atan(1.0)*4;
	scanf("%lf %lf %lf %lf %lf",&f,&R,&t,&r,&g);
	tr = R-t-f;
	ta = R*R*PI/4;
	ha=0;
	if(g>2*f) {
		for(i=0;;i++) {
			double nx=r+f+(g+2*r)*i;
			if(nx>tr) break;
			for(j=0;;j++) {
				double ny = r+f+(g+2*r)*j;
				if(nx*nx+ny*ny>=tr*tr) break;
				re = segment(max(nx,ny),min(nx,ny));
				ha += re;
			}
		}
	}

	
	_PE("Case #%d: %.8lf\n",_loop, 1-ha/ta);
}

まとめ

最初smallが通った後largeが通らず、誤差を疑ってなかなか通らず苦労した。
よく見たら外周の円弧の半径(R-t-f)の計算を間違っていた…。