はまやんはまやんはまやん

hamayanhamayan's blog

Compass Walking [AtCoder Beginner Contest 198 C]

https://atcoder.jp/contests/abc198/tasks/abc198_c

解説

https://atcoder.jp/contests/abc198/submissions/21692994

小数でよくある誤差に気を付けた実装をしていたらバグり散らかしてしまったが、
そこら辺を全く考えないコードでリライトしたら通った。
ABCであることを忘れてはいけない。

ちょうどRしか移動できない

この制限をどう扱うかがまず重要になる。
原点から目的地の距離が4で、R=2である場合は単純に4/2で2回が答えになる。
ピッタリの場合は問題ないが、原点から目的地の距離が5の場合はどうだろうか。
下界というか気持ち最小値を考えてみると、5/2の切り上げの3回である。
これは達成できるか?というのを考えてみると、反例が見つからない。
原点から目的地に最短距離で2進んで、そこから半径2の円を描いて、目的地から半径2の円を描いて交点を次の行き先にすれば3回が達成できる。
よって、距離/Rの切り上げが答えになりそうだ。

『コーナーケース』

この問題はコーナーケースがある。
コーナーケースとは、全体を支配する法則から乖離している一部分のことを指し、今回は「距離<Rの場合」である。
法則的には切り上げで1回であるが、1回でできるかを考えるとできないことが分かる。
この場合は少し回り道をして2回かかるので、これだけ別途扱うこと。

距離/Rの切り上げ

C++であればceilを使えば問題ないので、あとは計算する。

double R, X, Y;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> R >> X >> Y;

    double distance = sqrt(X * X + Y * Y);
    int ans = ceil(distance / R);
    if (ans == 1 && distance != R) ans++;

    cout << ans << endl;
}