POJ 2959 - Ball bearings

http://poj.org/problem?id=2959

概要

直径 D の大きい円の内側に接するように直径 d の小さい円を並べる．小さい円同士が少なくとも s 離れているようにしたとき，最大で何個の小さい円を並べることができるかを答える．

制約

10^-4 <= D, d, s <= 500
少なくとも 3 つの小さい円を並べることができる

解法

n 個の小さい円をちょうど s 離れるように並べたとき，それらに接する大きい円の直径は $\frac{s+d}{\sin\left(\frac{\pi}{n}\right)}+d$ なので，これが D 以下であればよい．

n >= 3 に注意してその不等式を解くと $n \le \frac{\pi}{\arcsin\left(\frac{s+d}{D-d}\right)}$ となり，これを計算するだけ．

 1 #include <cstdio>
 2 #include <cmath>
 3 using namespace std;
 4 static const double PI = acos(-1.0);
 5 
 6 int main()
 7 {
 8   int T;
 9   scanf("%d", &T);
10   while (T-- > 0) {
11     double D, d, s;
12     scanf("%lf %lf %lf", &D, &d, &s);
13     printf("%d\n", int(PI/asin((s+d)/(D-d))));
14   }
15   return 0;
16 }