【AtCoder】ABC 467 D - Concentric Circles

2026-07-19

AtCoder/ABC/D問題 AtCoder/ABC/425点問題 AtCoder/緑Diff AtCoder/NoviSteps/1Q AtCoder/数学/図形/円 AtCoder/数学/図形/垂直二等分線 AtCoder/数学/図形/ベクトルで考える競技プログラミング

D - Concentric Circles

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 928 / NoviSteps: 1Q / 配点: 425 点

問題概要

$xy$ 平面上に以下の条件を全て満たす $2$ 個の円 $C_1, C_2$ は存在するか判定せよ。ただし、 $C_1, C_2$ は同一である可能性があります。

異なる $2$ 点 $(P_x, P_y), (Q_x, Q_y)$ は $C_1$ の円周上にある。
異なる $2$ 点 $(R_x, R_y), (S_x, S_y)$ は $C_2$ の円周上にある。
$C_1$ と $C_2$ は中心が一致する。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めること。

制約

$1 \leq T \leq 5 \times 10^4$
$-10^9 \leq P_x,P_y,Q_x,Q_y,R_x,R_y,S_x,S_y \leq 10^9$
$(P_x, P_y) \neq (Q_x, Q_y)$
$(R_x, R_y) \neq (S_x, S_y)$
入力される値は全て整数

考察

条件の整理

まず、平面上の2点を通る円の中心は、その2点を結ぶ線分の垂直二等分線上にある。

したがって、線分 $\mathrm{PQ}$ の垂直二等分線と線分 $\mathrm{RS}$ の垂直二等分線が交点を持つならば、その交点を中心とする円 $C_1, C_2$ が存在する。

しかし、両者の垂直二等分線が交点を持たない(= 平行である)場合も、条件を満たす円が存在する場合がある。それは、2つの垂直二等分線が一致するときである。

つまり、線分 $\mathrm{PQ}$ と線分 $\mathrm{RS}$ の垂直二等分線が交点を持つか、もしくは一致するかを判定すればよい。

実装に向けて

ここまでの考察は中学数学範囲なのでそこまで難しくないが、問題は実装である。ここでは、線分の方向ベクトルに注目して考えることにする。

線分 $\mathrm{PQ}$ の方向ベクトルを $\bm{a}$ 、線分 $\mathrm{RS}$ の方向ベクトルを $\bm{b}$ とする。線分 $\mathrm{PQ}$ の垂直二等分線は $\bm{a}$ に垂直であり、線分 $\mathrm{RS}$ の垂直二等分線は $\bm{b}$ に垂直であるから、線分 $\mathrm{PQ}$ の垂直二等分線と線分 $\mathrm{RS}$ の垂直二等分線が交点を持つことは、 $\bm{a} \parallel \bm{b}$ であることと同値である。

これは2つのベクトルの外積が $0$ でなければ真である。

さて、 $\bm{a} \parallel \bm{b}$ でない場合について考えよう。

ここで、線分 $\mathrm{PQ}$ の中点を $\mathrm{M}_1$ 、線分 $\mathrm{RS}$ の中点を $\mathrm{M}_2$ とすると、両者の垂直二等分線が一致するためには、 $\mathrm{M}_2$ が線分 $\mathrm{PQ}$ の垂直二等分線上にあればよい( $\mathrm{M}_1$ についても同様)。

これは、線分 $\mathrm{M}_1 \mathrm{M}_2$ の方向ベクトルを $\bm{d}$ とすると、 $\bm{a} \perp \bm{d}$ であることと同値であり、 $\bm{a} \cdot \bm{d} = 0$ なら真である。

以上をまとめると、

$\bm{a} \times \bm{b} \neq 0$ ならば、Yes
$\bm{a} \times \bm{b} = 0$ $a \times b = 0$ であって、
- $\bm{a} \cdot \bm{d} = 0$ ならば、Yes
- それ以外なら、No

となる。

今回の解法における視覚的イメージを GeoGebra で作成したので、参考にしてほしい。

Calculator Suite - GeoGebra

Interactive, free online calculator from GeoGebra: graph functions, plot data, drag sliders, create triangles, circles and much more!

www.geogebra.org

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.using ll = long long;
5. 
6.// ======================================== //
7. 
8.struct Point {
9.    ll x, y;
10.};
11. 
12.ll dot_product(Point A, Point B)
13.{
14.    return A.x * B.x + A.y * B.y;
15.}
16. 
17.ll cross_product(Point A, Point B)
18.{
19.    return A.x * B.y - A.y * B.x;
20.}
21. 
22.bool solve() {
23.    Point P, Q, R, S;
24.    cin >> P.x >> P.y >> Q.x >> Q.y >> R.x >> R.y >> S.x >> S.y;
25. 
26.    ll ax = Q.x - P.x;
27.    ll ay = Q.y - P.y;
28.    ll bx = S.x - R.x;
29.    ll by = S.y - R.y;
30. 
31.    if (cross_product({ ax, ay }, { bx, by }) != 0) {
32.        return true;
33.    }
34. 
35.    ll dx = (R.x + S.x) - (P.x + Q.x);
36.    ll dy = (R.y + S.y) - (P.y + Q.y);
37.    if (dot_product({ ax, ay }, { dx, dy }) == 0) {
38.        return true;
39.    }
40.    else {
41.        return false;
42.    }
43.}
44. 
45.int main()
46.{
47.    int T;
48.    cin >> T;
49. 
50.    while (T--)
51.    {
52.        cout << (solve() ? "Yes" : "No") << endl;
53.    }
54. 
55.    return 0;
56.}