https://atcoder.jp/contests/abc181/tasks

F - Silver Woods

 

题意：二维平面上有上边界 y=100y=100 和下边界 y=−100y=-100，在两个边界中间还有一些点，有一个圆要从 (−109,0)(-10^9,0) 移动到 (109,0)(10^9,0)，可以沿任何方向移动，但是不能穿过点或者边界，问最大可行的圆的半径。

二分+并查集

二分答案。对于一个已知半径的圆，要判断能否成功移动到目标。

在刘汝佳平面图最小割那部分有一道叫动物园啥的题，讲的就是判断能否从起点到达目标点。有一个很妙的方法。

遍历所有点，如果到上边界距离小于圆的直径则该点向上边界连边，下边界类似。对于一对点，如果它们距离小于直径，则连边。

判断如果上边界存在路径到达下边界，则说明这一个带形区域被分割成了两块，这两块完全不互通，那么这个圆就没法到达目标点。

否则一定能够到达，实际上甚至可以到达任意点。

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
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const double eps = 1e-10;
int n;
double x[N], y[N];
int par[N];
void init(int n) { for (int i = 1; i <= n; i++)par[i] = i; }
int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
void uni(int x, int y) { par[find(x)] = find(y); }
bool ck(double r) {
	init(n + 2);
	for (int i = 1; i <= n; i++) {
		if (100 - y[i] < 2*r)uni(i, n + 1);
		if (y[i] + 100 < 2*r)uni(i, n + 2);
		for (int j = i + 1; j <= n; j++) {
			if ((x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j]) < 4 * r*r)uni(i, j);
		}
	}
	if (find(n + 1) == find(n + 2))return false;
	else return true;
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lf%lf", &x[i], &y[i]);
	}
	double L = 0, R = 100;
	while (R - L > eps) {
		double mid = (L + R) / 2;
		if (ck(mid))L = mid;
		else R = mid;
	}
	printf("%.9lf\n", L);
	return 0;
}