Codeforces #199 Div2. C. Cupboard and Balloons

CF199はDiv2 onlyなので本番参加は無く練習のみ。
http://codeforces.com/contest/342/problem/C

問題

図形問題なので上記URLの図を参照した方が良い。
幅2R×高さHの長方形の上に、半径Rの半円を乗せた図形がある。
ここに半径R/2の円をできるだけ詰め込みたい。
最大何個詰め込めるか。

解法

長方形部分には円を2個横に並べる幅がある。
よって、高さが円の高さのR未満になるまで、下から2個ずつ並べていく。

残された長方形の高さがR未満になった場合、以下のようになる。

1. 残り高さがR×√3/2以上あれば、もう2個下に並べた後で上にもう1つ置ける。
2. 残り高さがR×√3/2未満R/2以上あれば、もう2個下に並べられる。
3. 残り高さがR/2未満なら、1個上における。

以下のコードでは、2で割っても整数処理できるよう最初にH,Rを2倍している。

int R,H;

void solve() {
	int f,i,j,k,l, x,y;
	int r=0;
	cin>>R>>H;
	R*=2; H*=2;
	while(H>=R) {
		r+=2;
		H-=R;
	}
	if(H>=R/2) {
		r+=2;
		if(H>=sqrt(3)*R/2) r++;
	}
	else r++;
	_P("%d\n",r);
	
}

まとめ

最初解いたときは、R/2前後の場合分けにしか気づかず、R×√3/2に気づくまで少し時間がかかった。