书上给出了详细的思路，通过DFS判断，若连通上下边界就不能通过，若连通左右就更新解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 1010;
int n;
bool vis[maxn];
double left, right;
struct node {
double x,y,r;
bool inter(node a) {
double dx = x - a.x, dy = y - a.y;
return dx * dx + dy * dy - (r + a.r) * (r + a.r) <= 0;
}
} a[maxn];
bool dfs(int cur) {
vis[cur] = true;
if (a[cur].y - a[cur].r <= 0) return false;
if (a[cur].x - a[cur].r <= 0)
left = min(left, a[cur].y - sqrt(a[cur].r * a[cur].r - a[cur].x * a[cur].x));
if (a[cur].x + a[cur].r >= 1000)
right = min(right, a[cur].y - sqrt(a[cur].r * a[cur].r - (1000 - a[cur].x) * (1000 - a[cur].x)));
for (int i = 0; i < n; ++i) {
if (vis[i]) continue;
if (a[cur].inter(a[i]))
if(!dfs(i)) return false;
}
return true;
}
void solve() {
left = right = 1000;
for (int i = 0; i < n; ++i) {
if(!vis[i] && a[i].y + a[i].r >= 1000)
if(!dfs(i)) {
puts("IMPOSSIBLE");
return;
}
}
printf("0.00 %.2lf 1000.00 %.2lf\n", left, right);
}
int main() {
while (~scanf("%d", &n)) {
memset(vis, 0, sizeof(vis));
for (int i = 0; i < n; ++i)
scanf("%lf%lf%lf", &a[i].x, &a[i].y, &a[i].r);
solve();
}
return 0;
}
|
** 本文迁移自我的CSDN博客，格式可能有所偏差。 **