小O的平面画圆

[题目链接](https://www.nowcoder.com/practice/bb64967dbb2c430f8ff00e9be1c360c5)

思路

给定平面上 个圆，找出其中一个与所有其他圆都没有交点的圆。题目定义：两圆包含或相离视为没有交点（即相切也算有交点）。

两圆关系判断

设两圆圆心距为 ，半径分别为 和 。两圆的位置关系：

条件	关系	交点数
	外离	0
	外切	1
$\	r_1 - r_2\	< d < r_1 + r_2$	相交	2
$d = \	r_1 - r_2\	$	内切	1
$d < \	r_1 - r_2\	$	内含	0

根据题目定义，没有交点的条件为：（外离）或 （内含），即：

$$

避免浮点误差

由于输入均为整数，计算 以及 、 均为整数，可以完全避免浮点运算，使用整数比较即可。

注意坐标和半径最大值需要关注范围，避免整数溢出，使用 long long（或 Java 的 long）。

算法

暴力枚举每个圆 ，检查它是否与所有其他圆 都无交点。时间复杂度 。

样例演示

输入 3 个圆：圆1 (1,1,1)，圆2 (2,2,2)，圆3 (3,3,5)。

• 圆1 vs 圆2：，，。，相交，圆1不满足。
• 圆3 vs 圆1：，，。，内含（无交点）。
• 圆3 vs 圆2：，，。，内含（无交点）。

圆3与所有其他圆均无交点，输出 3。

代码

C++

#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;

    vector<long long> x(n), y(n), r(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i] >> r[i];
    }

    for (int i = 0; i < n; i++) {
        bool valid = true;
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            long long dx = x[i] - x[j];
            long long dy = y[i] - y[j];
            long long dist2 = dx*dx + dy*dy;
            long long sumR = r[i] + r[j];
            long long diffR = r[i] - r[j];
            if (dist2 > sumR * sumR || dist2 < diffR * diffR) {
                continue;  // 无交点，继续检查
            } else {
                valid = false;  // 有交点，此圆不满足
                break;
            }
        }
        if (valid) {
            cout << i + 1 << endl;
            return 0;
        }
    }

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

Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());

        long[] x = new long[n], y = new long[n], r = new long[n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            x[i] = Long.parseLong(st.nextToken());
            y[i] = Long.parseLong(st.nextToken());
            r[i] = Long.parseLong(st.nextToken());
        }

        for (int i = 0; i < n; i++) {
            boolean valid = true;
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                long dx = x[i] - x[j];
                long dy = y[i] - y[j];
                long dist2 = dx*dx + dy*dy;
                long sumR = r[i] + r[j];
                long diffR = r[i] - r[j];
                if (dist2 > sumR * sumR || dist2 < diffR * diffR) {
                    continue;
                } else {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                System.out.println(i + 1);
                return;
            }
        }

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

复杂度分析

• 时间复杂度：，枚举每对圆的关系。
• 空间复杂度：，存储圆的信息。