ABC 467 D - Concentric Circles

[river0525]

問題の感想や気づきを投稿・共有するスペースです

[daikusutora3]

円1 (x-a)^2 + (x-b)^2 = r1^2
円2 (x-a)^2 + (x-b)^2 = r2^2

の式を考える。円1に2頂点を代入して計算するとr1の項が消せる、同様に円2に2頂点を代入して計算するとr2の項が消せる。

するとaとbに関する方程式が2本出てくるので、実際にaとbを計算して解が出てくるかどうかを判定すればOK。具体的には以下の2式が出てくる。

1. A*a = B
2. C*b = D

ここで A == 0 and B != 0 または C == 0 and D != 0 ならば答えはNoで、それ以外なら答えはYes

上記のように方程式ベースで解きました！

[AXT-AyaKoto]

もとの問題
→ 「P, Qの2点から同じ距離」「R, Sの2点から同じ距離」を同時に満たす点はあるか？
→ 「線分PQの垂直二等分線」と「線分RSの垂直二等分線」の両方が通る点はあるか？
→ 2つの垂直二等分線が平行でない(パターンA)か、2つの垂直二等分線が実は同じ線(パターンB)かのいずれかを満たすか？
のように読み替える。
パターンAは、垂直二等分線同士が平行ならもとのPQとRSも平行なので、PQとRSの平行判定をすればいい。(私はベクトルを使いました)
パターンBだが、PQとRSが平行であることは(先にAを処理すれば)確定するので、これを前提とした判別方法を考える。
垂直二等分線同士に共有点があればよくて、「PQの中点(PQの垂直二等分線は定義上ここを通る)がRSの垂直二等分線上にあるか」を判定するのが良い。
RSの垂直二等分線上にあるということはRからもSからも距離が等しいということになるので、ベクトル作って大きさだけ比較すればいい(オーバーフローに注意)。

// 提出: https://atcoder.jp/contests/abc467/submissions/77668059
// https://jsr.io/@ayaexptech/arcane/doc/~/Vector2D が使用可能であることを仮定
const pt_P = new Vector2D(Px, Py);
const pt_Q = new Vector2D(Qx, Qy);
const pt_R = new Vector2D(Rx, Ry);
const pt_S = new Vector2D(Sx, Sy);
const vec_PQ = pt_Q.sub(pt_P);
const vec_RS = pt_S.sub(pt_R);
if (vec_PQ.cross(vec_RS) !== 0) {
    console.log("Yes");
} else {
    const pt_PQ_mid_2x = pt_P.add(pt_Q);
    const pt_R_2x = pt_R.mul(2);
    const pt_S_2x = pt_S.mul(2);
    const vec_PQ_mid_R_2x = pt_R_2x.sub(pt_PQ_mid_2x);
    const vec_PQ_mid_S_2x = pt_S_2x.sub(pt_PQ_mid_2x);
    if (vec_PQ_mid_R_2x.squaredMagnitude() === vec_PQ_mid_S_2x.squaredMagnitude()) {
        console.log("Yes");
    } else {
        console.log("No");
    }
}

本番中はパターンBを「PQ中点からRS中点へのベクトルが直角に交わる(内積が0)ならYes」と捉えていました。今振り返ると若干危ない。

[Yuulis]

GeoGebraでベクトルを使って解くときのイメージを視覚化しました。

https://www.geogebra.org/calculator/ryaehqbm

実装例: https://atcoder.jp/contests/abc467/submissions/77605639

解法詳細はブログに書きました。
https://yuulisio.com/posts/review-abc467-d