POJ 2959 Ball bearings

問題

直径Dの円に内接する複数の直径dの小円を考える。小円同士の中心が少なくともs+d以上離れているように配置したい。最大でいくつの小円を配置できるか。

やりかた

配置する間隔は等間隔にする。間隔は円の個数に対して単調減少なので二分探索できる。C個置けるとすると隣り合う円の中心同士の距離は(D -d) * sin(π/C)になるのでこれがs+d以上になるかに関して二分探索する。

以下ソース。

int main(int argc, char **argv){
  int N; cin >> N;
  while(N--){
    double s, D, d;
    cin >> D >> d >> s;
    double ub = 1e10, lb = 0;
    for(int i = 0; i < 100; i++){
      double mid = (ub + lb) / 2.0;
      double dist = (D - d) * sin(3.14159265359 / mid);
      if(dist + EPS < d + s) ub = mid;
      else lb = mid;
    }
    cout << floor(ub) << endl;
  }
  return 0;
}