AOJ2131 Pi is Three

問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2131

π-R <= P <= π+R となるような有理数Pの既約分数について考える。
分母を最小化して、同じ分母であれば、πにできるだけ近い値を求めよ。
R <= 1.0

解法
分母を1から総当りして、条件の範囲に収まるPが存在するかを判定する。
存在するならば、π-R, π+Rを元に上限と下限を決めて二分探索すれば良い。

実際、条件の範囲に収まるPが存在するかの判定は、二分探索するときに条件を1度以上満たしたかどうかを記憶しておけば良い。

double const PI = acos(-1);
 
int solve(int deno, double R) {
  int L = (PI-R) * deno, U = ceil(PI+R) * deno;
  bool ok = 0;
  while(U-L > 1) {
    int M = (L + U) / 2.0;
    if(abs(double(M) / deno - PI) <= R) {
      ok = 1;
      L = M;
    } else {
      U = M;
    }
  }
  return ok ? L : -inf;
}
 
int main() {
 
  double R;
  while(cin >> R && R != 0.0) {
    rep(deno, 10000000) {
      int n = solve(deno+1, R);
      if(n != -inf) {
        printf("%d/%d\n", n, deno+1);
        break;
      }
    }
  }
   
  return 0;
}