【AtCoder】ABC 460 B - Two Rings

2026-06-08

AtCoder/ABC/B問題 AtCoder/ABC/250点問題 AtCoder/灰Diff AtCoder/NoviSteps/4Q AtCoder/数学/図形問題/円競技プログラミング

B - Two Rings

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

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 128 / NoviSteps: 4Q / 配点: 250 点

問題概要

$xy$ 平面上に $2$ つの円 $C_1, C_2$ がある。円 $C_1$ は中心の座標が $(X_1, Y_1)$ で半径が $R_1$ 、円 $C_2$ は中心の座標が $(X_2, Y_2)$ で半径が $R_2$ である。

円 $C_1$ と円 $C_2$ が共有点を持つかどうかを判定せよ。なお、 $T$ 個のテストケースが与えられるのでそれぞれについて答えを求めること。

制約

$1 \leq T \leq 100$
$0 \leq X_1, Y_1, X_2, Y_2 \leq 10^9$
$1 \leq R_1, R_2 \leq 10^9$
入力される値は全て整数

考察

$C_1$ と $C_2$ の中心間距離を $d$ とすれば、2円が共有点を持つための必要十分条件は

|R_1 - R_2| \leq d \leq R_1 + R_2

である。

しかし、このままだと $d$ は小数になり、大小比較時に誤差が発生する可能性があるため、各項が正であることを利用して両辺を二乗する。

(R_1 - R_2)^2 \leq d^2 \leq (R_1 + R_2)^2

したがって、この条件を満たすかどうかをテストケースごとに判定すればよい。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.using ll = long long;
5. 
6.// ======================================== //
7. 
8.bool solve()
9.{
10.    ll X1, Y1, R1, X2, Y2, R2;
11.    cin >> X1 >> Y1 >> R1 >> X2 >> Y2 >> R2;
12. 
13.    ll d2 = (X1 - X2) * (X1 - X2) + (Y1 - Y2) * (Y1 - Y2);
14.    ll diff2 = (R1 - R2) * (R1 - R2);
15.    ll sum2 = (R1 + R2) * (R1 + R2);
16. 
17.    if (diff2 <= d2 && d2 <= sum2)
18.        return true;
19.    else
20.        return false;
21.}
22. 
23.int main()
24.{
25.    int T;
26.    cin >> T;
27. 
28.    while (T--)
29.    {
30.        cout << (solve() ? "Yes" : "No") << endl;
31.    }
32. 
33.    return 0;
34.}

Submission #76417542 - AtCoder Beginner Contest 460

Submission #76417542 - AtCoder Beginner Contest 460

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

実装時間: 5 分以内

コメント

参考:

2つの円の位置関係 | 高校数学の美しい物語

2つの円の位置関係 | 高校数学の美しい物語

2つの円の位置関係５パターンの整理。共通接線，交点の数，中心間の距離，相似の中心まで性質をまとめました。

高校数学の美しい物語