ABC198 C 解答

C - Compass Walking(413)

問題文

2 次元平面上の原点に高橋君がいます。
高橋君が 1 歩歩くと、いまいる点からのユークリッド距離がちょうど R であるような点に移動することができます(移動先の座標が整数である必要はありません)。これ以外の方法で移動することはできません。高橋君が点 ( X, Y )に到達するまでに必要な歩数の最小値を求めてください。なお、点 (x1, y1) と点 (x2, y2)のユークリッド距離は√{(x1−x2)^2+(y1−y2)^2}で与えられます。

制約

1 ≤ R ≤ 10^5
0 ≤ X, Y ≤ 10^5 
(X, Y) ≠ (0, 0)
入力は全て整数

考察

浮動小数点誤差をどうにかする問題です。

ですが、まずは誤差を気にせずに考えてみましょう。

１歩で R 動けますので、２歩で2Rです。当然、3 歩で 3R です。3R であれば 3R 以下の距離の全ての場所にぴったりと止まることが可能です。

2点からコンパスで半径 R の円を書いてその交点を経由する

と考えるとわかりやすいのでしょうか。

N 歩だと NRですので、これを目的地までの距離と比べてあげましょう。

NR ≧ √(x^2+y^2)
N ≧ √(x^2+y^2) / R

これが成立する最小値が答えとなります。ですので、

N = √(x^2+y^2) / R

ですね（切り上げです）。目的地までの距離を一回の移動距離で割れば良さそうです。ここで、誤差を気にしなければこれでOKです。

ここから、誤差について考えましょう。

NR ≧ √(x^2+y^2)

この式が良さそうです。ルートを計算すると小数点から逃げられないので、消しちゃいましょう。この不等式の両辺とも正なので2乗します。

N * N * R * R ≧ x * x + y * y

この式が成立する N の最小値が誤差のない答えとなります。

R, X, Yは入力として与えられますので、N を 1 から順番に増やして判定をしていきましょう。幸いなことに、最大ケース（R=1, X=10^5, Y=10^5）のときにも、2 * 10^5 程度に収まりますので、十分に探索することが可能です。

これで誤差なく実装することができました。

最後にコーナーケースです。上の方で、NR以下の場所には N 回でぴったり止まれると書きましたが、 N = 1の場合だけはちょいと異なります。距離が R 未満の場所はどうやっても通り過ぎてしまうのです。ですので、一旦遠くに行ったのち、戻ってくるので、2歩必要になります。注意しましょう。

実装

 #include <bits/stdc++.h> #define  rep(i,n) for(int i=0;i<n;++i) #define  reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main()
{
   ll r,x,y;
   cin >> r >> x >> y;
   r *= r;
   ll d = x*x + y*y;
   ll ans = 1;
   //上記の式が成立するまでansを増やす。
   while(d > r * ans*ans) ++ans;
   //ansが1のときに一歩でぴったりいけないのなら+1する。
   if(ans == 1)
   {
       if(d!= r) ++ans;
   }
   cout << ans << endl;
   return 0;
}

あとがき

誤差問題でした。ただこの問題はN=1のコーナーケースもありますので、誤差で間違えているのか、コーナーケースにはまっているのか、そもそもコーナーケースの存在に気づかないのか、解いてる最中は色々な不安に駆られる問題だったのではないでしょうか。問題文がシンプルなだけに余計にそわそわしてしまいます。

様々なケースを考慮して、こういう問題こそWAを出さずに突破できるようになりたいですね。