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

hamayanhamayan's blog

Circumferences [AtCoder Beginner Contest 259 D]

競技プログラミング

https://atcoder.jp/contests/abc259/tasks/abc259_d

前提知識

解説

https://atcoder.jp/contests/abc259/submissions/33122718

今回の問題は前提として、幾何の以下の判定方法を知っている必要がある

問題を分割しながら、要求されていることをかみ砕いていく

今はどうか分からないが、ICPCではよくこのような問題が出ていた。
問題を分割して、個別に解決していくことにしよう。

まずは、点Sから点Tに行くことができるかという部分について考えてみよう。
入力例1の図で考えてみると、
点S -> 青い円 -> 赤い円 -> 緑の円 -> 点T
のような流れで行くことができている。
無意識に図を見て、このように判断しているが、判断を分割化してみよう。

まず、点Sがどの円の上にあるかがまず気になる所である。
で、どの円にあるか、というのが特定できたら、次はその円と交わっている円を探しているはずだ。
で、交わっている円から直感的に点Sに近くなりそうな円を使って移動して、点Tに最終的に移動している。

点Sが青い円にあることはすぐに分かるし、点Tが緑の円にあることもすぐわかる。
かつ、点がどこにあるかというのはそれほど問題ではなく、点が乗っている円が特定できたら、
後はその始点となる円から終点となる円に交差している円を通って移動可能かだけが問題となる。

何が必要？

今書いたようなことは分かるわいという人も多いかもしれない。
必要とされていることを書き下してみよう

  • とある点がどの円の上にあるかを特定する
  • 与えられている円と円が交差しているかどうかを判定する
  • とある円からとある円に対して交差している円を通って到達可能かを判定する

上2つは幾何的な知識があれば、解決できるが、最後はどうだろうか。
到達可能性判定と言えばBFSだが、BFSといえばグリッドとかグラフとかだけど…

到達可能性判定、グラフの問題に帰着させる

グラフの問題に帰着させることができる。
（わざわざグラフと解釈しないでそのまま解いてもいいんだけれども）
円をグラフの頂点と考えることにする。
そして、頂点間の辺は移動可能ならつなげるようにする。
移動可能というのは2つの頂点、つまり、円が交差しているときであるため、交差しているなら、2つの頂点間に辺を張る。
すると無向グラフが出来上がり、点Sがある円に対応する頂点が始点で、点Tがある円に対応する頂点が終点となる。

あとは、このグラフ上でBFSをしながら、始点から終点に到達可能かを判定すれば答えを導くことができる。

実装に関する注意点

幾何問題なので、自分は幾何ライブラリを持ってきてしまったが、今回の判定は全部整数で行うことができ、下手にdoubleを経由するとWAだった。
2点間の距離を良く求めることになるかと思うが、例えば、円上に点があるかの判定のときに

(とある円の中心とチェックしたい点との距離) == (とある円の半径)

をチェックしたいと思うが、左辺は平方根を取るため、整数に収まらない。
よって、誤差を最小化するよう、整数でチェックするために、どちらも二乗をして、

(とある円の中心とチェックしたい点との距離)2 == (とある円の半径)2

で判定すること。
「与えられている円と円が交差しているかどうかを判定する」ときも同様に二乗した状態で判定することにしよう。
intだとオーバーフローするのでlong longを利用すること。

実装については自分の実装も参考にしてみてほしい。

int N;
ll sx, sy, tx, ty;
ll x[3010], y[3010], r[3010];

int getCircleOn(int px, int py) {
    rep(i, 0, N) {
        ll dist2 = abs(px - x[i]) * abs(px - x[i]) + abs(py - y[i]) * abs(py - y[i]);
        if (dist2 == r[i] * r[i]) return i;
    }
    return -1;
}

#define YES "Yes"
#define NO "No"
string solve() {
    int start = getCircleOn(sx, sy);
    int end = getCircleOn(tx, ty);

    //
    // makeEdges
    // ================================
    vector<int> E[3010];
    rep(i, 0, N) rep(j, i + 1, N) {
        ll dist2 = abs(x[i] - x[j]) * abs(x[i] - x[j]) + abs(y[i] - y[j]) * abs(y[i] - y[j]);

        if ((r[i] + r[j]) * (r[i] + r[j]) < dist2) continue;
        if (dist2 < abs(r[i] - r[j]) * abs(r[i] - r[j])) continue;

        E[i].push_back(j);
        E[j].push_back(i);
    }

    //
    // checkReachable
    // ================================
    queue<int> que;
    set<int> visited;

    que.push(start);
    visited.insert(start);

    while (!que.empty()) {
        int cu = que.front();
        que.pop();

        if (cu == end) return YES;

        fore(to, E[cu]) if (!visited.count(to)) {
            que.push(to);
            visited.insert(to);
        }
    }

    return NO;
}

void _main() {
    cin >> N >> sx >> sy >> tx >> ty;
    rep(i, 0, N) cin >> x[i] >> y[i] >> r[i];
    cout << solve() << endl;
}