[AtCoder] ABC 198 C – Compass Walking

2021年4月12日

問題

方針

原点と \( (X, Y) \) の距離を \( d \) とすると、\( d = \sqrt{X^2 + Y^2} \) であるので、\( d \) が自然数で \( d \bmod R = 0 \) であるとき、

\[ \dfrac{d}{R}\]

が最小の歩数となります。 次に、\( d < R \) であるときを考えると、\( 2 \) 歩で到達できることが分かります。そうではないときを考えます。

原点と \( (X, Y) \) を結ぶ直線上を歩くことを考えます。ここで、\( kR < d < (k + 1)R \) を満たす \( k \) をついて、\( k – 1 \) 歩までこの直線を \( (X, Y)\) に向かって歩いたとすると、\( R < d – (k – 1)R < 2R \) となるので、あと\( 2 \) 歩で到達できることが分かります。したがって、

\[ \left \lceil \dfrac{d}{R} \right \rceil\]

が最小の歩数となります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ll R, X, Y;
    cin >> R >> X >> Y;
    double d = sqrt(X * X + Y * Y);
    ll l = floor(d);
    if (floor(d) == ceil(d) && l % R == 0) {
        cout << l / R << "\n";
    } else if (d < R) {
        cout << 2 << "\n";
    } else {
        cout << l / R + 1 << "\n";
    }
    return 0;
}