UVa 10969 Sweet Dream

题目描述

你站在房间中央，手里拿着一堆大小不一的圆盘。你可以随机选择一个圆盘并扔到地板上，重复此过程直到手上没有圆盘。圆盘落地后，有些圆盘会被后来的圆盘部分（或完全）覆盖。

你的任务是：从上方观察，计算所有圆盘可见部分的周长总和。

图 1 展示了圆盘相互覆盖的情况（此处省略图片，但可想象为若干圆形互相重叠，上层圆盘遮挡下层圆盘的部分区域）。

输入格式

第一行是一个整数 $T\le 100$，表示测试用例的数量。

每个测试用例的第一行是一个整数 $N\le 100$，表示圆盘的数量。

接下来 $N$ 行，每行包含三个浮点数：$r_k\le 100000$（半径），以及 $-100000\le x_k,y_k\le 100000$（圆心坐标）。

如果两个浮点数的绝对差小于 $10^{-10}$，则认为它们相等。

输出格式

对于每个测试用例，输出一行一个浮点数，表示从上方可见的圆盘周长总和，四舍五入保留三位小数。

输出必须恰好有三位小数。

样例

输入

3
1
10 0 0
2
5 0 0
10 0 0
2
100 110

输出

62.832
62.832
10.472

题目分析

本题的核心是：给定若干个圆盘，按照输入顺序依次落到地面上（后输入的圆盘落在先输入的圆盘之上）。最终，从上往下看时，每个圆盘只能看到没有被任何后来的圆盘遮挡的部分。我们需要计算所有圆盘可见部分的总周长。

关键点分析

解题思路

1. 几何建模

设圆盘 $i$ 的圆心为 $O_i$，半径为 $R_i$；圆盘 $j$（$j>i$）的圆心为 $O_j$，半径为 $r_j$。

圆心距：$d=|O_i{O}_j|$。

如果两圆相交，则圆盘 $i$ 被圆盘 $j$ 遮挡的弧段对应的半角 $\theta$ 满足：

$$\cos \theta =\frac{R_i^2+d^2-r_j^2}{2R_{i}d}$$

其中 $\theta \in [0,\pi ]$。这个公式来源于三角形 $O_i{O}_{j}P$（$P$ 为两圆交点），由余弦定理得到。

遮挡区间相对于向量 $O_i{O}_j$ 的方向角 $\alpha =\text{atan2}(dy,dx)$ 对称分布，即区间为 $[\alpha -\theta ,\alpha +\theta ]$。

2. 区间标准化与合并

由于极角区间可能跨越 $0$ 或 $2\pi$，我们需要将其标准化到 $[0,2\pi )$。具体做法是：

• 若 $l<0$，拆分为 $[l+2\pi ,2\pi )$ 和 $[0,r]$。
• 若 $r>2\pi$，拆分为 $[l,2\pi )$ 和 $[0,r-2\pi ]$。

然后对所有区间按左端点排序，依次合并重叠或相邻的区间，得到总覆盖弧度。

3. 算法流程

对于每个测试用例：

4. 复杂度分析

• 每个测试用例有 $N$ 个圆盘，对每个圆盘 $i$ 需要检查 $N-i$ 个后来的圆盘。
• 每次检查 $O(1)$ 时间。
• 区间合并：最多 $O(N)$ 个区间，排序 $O(N\log N)$。
• 总时间复杂度：$O(N^2+N^2\log N)=O(N^2\log N)$，在 $N\le 100$ 时完全可行。

代码实现

// Sweet Dream
// UVa ID: 10969
// Verdict: Accepted
// Submission Date: 2026-06-11
// UVa Run Time: 0.000s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

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

const double PI = acos(–1.0);
const double EPS = 1e-10;

struct Circle { double x, y, r; };

double normAngle(double a) {
while (a < 0) a += 2 * PI;
while (a >= 2 * PI) a -= 2 * PI;
return a;
}

vector<pair<double, double>> addInterval(vector<pair<double, double>> &intervals, double l, double r) {
if (r – l > 2 * PI + EPS) {
intervals.emplace_back(0, 2 * PI);
return intervals;
}
l = normAngle(l);
r = normAngle(r);
if (l < r) intervals.emplace_back(l, r);
else {
intervals.emplace_back(l, 2 * PI);
intervals.emplace_back(0, r);
}
return intervals;
}

double mergeAndGetCovered(vector<pair<double, double>> &intervals) {
if (intervals.empty()) return 0.0;
sort(intervals.begin(), intervals.end());
double covered = 0.0;
double curL = intervals[0].first, curR = intervals[0].second;
for (size_t i = 1; i < intervals.size(); i++) {
if (intervals[i].first <= curR + EPS) {
curR = max(curR, intervals[i].second);
} else {
covered += curR – curL;
curL = intervals[i].first;
curR = intervals[i].second;
}
}
covered += curR – curL;
return covered;
}

int main() {
int T;
scanf("%d", &T);
while (T—) {
int N;
scanf("%d", &N);
vector<Circle> c(N);
for (int i = 0; i < N; i++) {
scanf("%lf%lf%lf", &c[i].r, &c[i].x, &c[i].y);
}

double ans = 0.0;

for (int i = 0; i < N; i++) {
vector<pair<double, double>> blocked;

for (int j = i + 1; j < N; j++) {
double dx = c[j].x – c[i].x, dy = c[j].y – c[i].y;
double d = sqrt(dx * dx + dy * dy);
double R = c[i].r, r = c[j].r;

if (d + R <= r + EPS) {
blocked.clear();
blocked.emplace_back(0, 2 * PI);
break;
}
if (d + r <= R + EPS || d >= R + r – EPS)
continue;

double ang = atan2(dy, dx);
double theta = acos((R * R + d * d – r * r) / (2 * R * d));
addInterval(blocked, ang – theta, ang + theta);
}

double covered = mergeAndGetCovered(blocked);
ans += (2 * PI – covered) * c[i].r;
}

printf("%.3lf\\n", ans);
}
return 0;
}

总结

本题是一个计算几何与区间合并相结合的典型问题。关键点包括：

技巧总结：

• 将几何问题转化为区间覆盖问题，是处理圆形遮挡问题的常用方法。
• 对于极角区间，标准化到 $[0,2\pi )$ 后，跨越 $2\pi$ 的情况可以通过拆分区间来处理。
• 按照输入顺序（即掉落顺序）处理遮挡关系，可以自然地保证后落的圆盘覆盖先落的圆盘。

本题虽小，但涵盖了计算几何、区间算法和精度控制等多个知识点，是一道很好的综合练习题。