题解 | #小O的平面画圆#

题目链接

小O的平面画圆

题目描述

平面上有 $n$ 个圆，每个圆由其圆心坐标 $(x, y)$ 和半径 $r$ 定义。你需要找到一个圆，它与其他所有的圆都没有交点。

我们定义，两个圆没有交点的情况包括：一个圆完全包含在另一个圆内部，或者两个圆完全分离（相离）。反之，如果两个圆相切（内切或外切）或有两个交点，则视为有交点。

若存在这样的圆，输出其（从1开始的）编号；若有多个答案，输出任意一个即可。若不存在，则输出 -1。

解题思路

题目的核心是判断一个给定的圆是否与其它所有圆都不相交。我们可以对每个圆进行逐一检验。

1. 判断两圆关系

考虑任意两个圆，圆 $i$ 和圆 $j$ ，其圆心分别为 $(x_i, y_i)$ 和 $(x_j, y_j)$ ，半径分别为 $r_i$ 和 $r_j$ 。

首先，计算它们圆心之间的距离 $d$ 。为了避免开方运算可能带来的浮点数精度问题，我们转而使用距离的平方 $d^2$ 进行计算： $d^2 = (x_i - x_j)^2 + (y_i - y_j)^2$
两个圆有交点（即相交或相切）的几何条件是：圆心距 $d$ 同时满足 $d \ge |r_i - r_j|$ 和 $d \le r_i + r_j$ 。
将这个条件同样用平方形式表示，可以避免比较浮点数，从而更加精确和高效。两圆有交点的条件等价于： $(r_i - r_j)^2 \le d^2 \le (r_i + r_j)^2$
因此，两圆没有交点（相离或内含）的条件就是上述条件的否定： $d^2 > (r_i + r_j)^2$ (相离) 或 $d^2 < (r_i - r_j)^2$ (内含)

2. 算法流程

我们可以采用暴力枚举的方法，对每一个圆进行验证：

外层循环遍历每一个圆 $i$ (从 $1$ 到 $n$ )，将其作为候选答案。
对于每个候选圆 $i$ ，我们设置一个标志位 is_valid，初始为 true。
内层循环遍历所有其他圆 $j$ (从 $1$ 到 $n$ , 且 $j \ne i$ )。
在内层循环中，计算圆 $i$ 和圆 $j$ 之间的圆心距平方 $d^2$ ，以及半径和的平方 $(r_i + r_j)^2$ 与半径差的平方 $(r_i - r_j)^2$ 。
判断它们是否有交点，即是否满足 $(r_i - r_j)^2 \le d^2 \le (r_i + r_j)^2$ 。
- 如果满足此条件，说明圆 $i$ 与圆 $j$ 有交点，那么圆 $i$ 不是一个合法的答案。我们将 is_valid 设为 false，并立即跳出内层循环（因为已经找到了一个反例），去检验下一个候选圆。
当内层循环正常结束后（即没有因为找到交点而提前 break），我们检查 is_valid 标志位。
- 如果 is_valid 仍然为 true，说明候选圆 $i$ 与所有其他圆都没有交点。我们已经找到了答案，输出其编号 $i$ 并终止程序。
如果外层循环结束后仍未找到任何满足条件的圆，则说明不存在这样的圆，输出 -1。

注意: 计算平方值时，坐标和半径的差或和可能会超出标准 int 类型的范围，因此应使用 long long (C++) 或 long (Java) 来存储这些中间计算结果，以防溢出。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

struct Circle {
    long long x, y, r;
    int id;
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<Circle> circles(n);
    for (int i = 0; i < n; ++i) {
        cin >> circles[i].x >> circles[i].y >> circles[i].r;
        circles[i].id = i + 1;
    }

    for (int i = 0; i < n; ++i) {
        bool intersects_with_any = false;
        for (int j = 0; j < n; ++j) {
            if (i == j) {
                continue;
            }

            long long dx = circles[i].x - circles[j].x;
            long long dy = circles[i].y - circles[j].y;
            long long dist_sq = dx * dx + dy * dy;

            long long r_sum = circles[i].r + circles[j].r;
            long long r_sum_sq = r_sum * r_sum;

            long long r_diff = circles[i].r - circles[j].r;
            long long r_diff_sq = r_diff * r_diff;

            if (dist_sq <= r_sum_sq && dist_sq >= r_diff_sq) {
                intersects_with_any = true;
                break;
            }
        }
        
        if (!intersects_with_any) {
            cout << circles[i].id << endl;
            return 0;
        }
    }

    cout << -1 << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] x = new long[n];
        long[] y = new long[n];
        long[] r = new long[n];

        for (int i = 0; i < n; i++) {
            x[i] = sc.nextLong();
            y[i] = sc.nextLong();
            r[i] = sc.nextLong();
        }

        for (int i = 0; i < n; i++) {
            boolean intersectsWithAny = false;
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    continue;
                }

                long dx = x[i] - x[j];
                long dy = y[i] - y[j];
                long distSq = dx * dx + dy * dy;

                long rSum = r[i] + r[j];
                long rSumSq = rSum * rSum;

                long rDiff = r[i] - r[j];
                long rDiffSq = rDiff * rDiff;

                if (distSq <= rSumSq && distSq >= rDiffSq) {
                    intersectsWithAny = true;
                    break;
                }
            }
            if (!intersectsWithAny) {
                System.out.println(i + 1);
                return;
            }
        }

        System.out.println(-1);
    }
}

import sys

def solve():
    n = int(sys.stdin.readline())
    circles = []
    for i in range(n):
        x, y, r = map(int, sys.stdin.readline().split())
        circles.append((x, y, r, i + 1))

    for i in range(n):
        intersects_with_any = False
        for j in range(n):
            if i == j:
                continue

            x1, y1, r1, _ = circles[i]
            x2, y2, r2, _ = circles[j]

            dx = x1 - x2
            dy = y1 - y2
            dist_sq = dx * dx + dy * dy

            r_sum = r1 + r2
            r_sum_sq = r_sum * r_sum

            r_diff = r1 - r2
            r_diff_sq = r_diff * r_diff

            if r_diff_sq <= dist_sq <= r_sum_sq:
                intersects_with_any = True
                break
        
        if not intersects_with_any:
            print(circles[i][3])
            return

    print(-1)

solve()

算法及复杂度

算法: 暴力枚举、计算几何
时间复杂度: 算法采用两层嵌套循环来检查每一对圆是否相交。外层循环执行 $n$ 次，内层循环也执行 $n$ 次。循环体内的计算是常数时间操作。因此，总时间复杂度为 $\mathcal{O}(n^2)$ 。
空间复杂度: 我们需要存储 $n$ 个圆的圆心坐标和半径信息。因此，所需的额外空间与圆的数量成正比，空间复杂度为 $\mathcal{O}(n)$ 。