几何习题

二分

ABC181F Silver Woods

题意

有 \(n \le 100\) 个木桩在 \(-100\le y \le100\) 的范围里。你有一个圆，圆的半径你可以选择的。求可以把圆从最左边移动到最右边的最大半径。

思路

首先题目具有单调性：如果一个半径可以移动，那么更小的也可以。如果一个半径不能移动，那么更大的肯定不行。所以我们考虑二分。那给定一个 \(r\) 怎么检查呢。对于两个点\(x,y\)，如果 \(r\) 不能从他们之间通过，那么我们就将这两个点连起来。对于上下界\((y=\pm 100)\) 如果不能这个线和这个点之间穿过去，那么我们就连上他们。我们枚举把所有的点都连线完。如果存在一条由上界连向下界的边，那么这个半径就被 "拦住了"不能通过。如果没有就一定存在一条路径可以通过。所以我们用并查集连接就好了，最后检查一下上下界有没有连起来即可。

代码

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
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
typedef pair<int, int> pii;
typedef long long ll;
const int maxn = 100 + 5;
template<class T> void print(T & x){ cout << x; }
template<class T,class U> void print(pair<T,U> & p){cout << "("; print(p.first); cout << ", "; print(p.second); cout << ")"; }
template<class T> void print(vector<T> & v) {
    cout << "{";
    if (sz(v)) print(v[0]);
    for (int i = 1; i < sz(v); i++) cout << ", ", print(v[i]);
    cout << "}\n";
}


int n, m;
double x[maxn], y[maxn];

int fa[maxn];

int find(int x) {
    if (!~fa[x]) return x;
    return fa[x] = find(fa[x]);
}

void connect(int i, int j) {
    int fi = find(i); int fj = find(j);
    if (fi != fj) fa[fi] = fj;
}

double dist(int i, int j) {
    return (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]);
}
bool check(double k) {
    memset(fa, ~0, sizeof(fa));
    for (int i = 1;i <= n; ++i) {
        for (int j = i+1;j <= n;++j) {
            if (dist(i, j) < 4*k*k) connect(i, j);
        }
        if (abs(y[i] - 100) < 2*k) connect(n+1, i);
        if (abs(y[i] + 100) < 2*k) connect(n+2, i);
    }
    return find(n+1) != find(n+2);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1;i <= n; ++i) {
        cin >> x[i] >> y[i];
    }
    double L = 0, R = 100, M;
   
    while (R-L > 1e-5) {
        M = (L+R)/2;
        if (check(M)) L = M;
        else R = M;
    }
    cout << fixed << setprecision(5) << M << endl;
    return 0;
}