有点像最小割的感觉…

懵逼的 题目

扯淡的 题解

一开始想搞个对偶图最大生成树然后跑个LCA云云的做法…

题解有两种做法…

一个是二分可能的最大值, 把能”拦下”这个球的两个点之间连边, 然后用并查集判断一下上下边界是否联通就行了

第二个是把所有的边都连边, 然后跑最小生成树, 当上下边界联通的时候, 最后那条边的长度就是球的最大直径

沙茶的 代码

注意%f会给你自动四舍五入…

1 最小生成树

一开始想先跑出树来然后跑LCA云云

后来参照吴清月大爷的做法感觉肥肠简短Orz

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define MAXN (500 + 5)
#define DD double
#define pii pair<int, int>
const int s = 0, t = 501;
using namespace std;
struct edg
{
    int from, to;
    DD cost;
    edg() {}
    edg(int a, int b, DD c): from(a), to(b), cost(c) {}
}b[MAXN * MAXN];
int fa[MAXN], n, cntb, l;
pii a[MAXN];
int find(int x)
{ return (fa[x] == x) ? x : (fa[x] = find(fa[x])); }
void uni(int x, int y)
{ fa[find(x)] = find(y); }
bool cmp(edg x, edg y)
{ return x.cost < y.cost; }
DD caldis(int x0, int y0, int x1, int y1)
{ return sqrt((x0 - x1) * (x0 - x1) + (y0 - y1) * (y0 - y1)); }
void solve()
{
    sort(b + 1, b + cntb + 1, cmp);
    for (int i = s; i <= t; i++)    fa[i] = i;
    for (int i = 1; i <= cntb; i++)
        if (find(b[i].from) != find(b[i].to))
        {
            uni(b[i].from, b[i].to);
            if (find(s) == find(t))
            {
                printf("%.3lf", b[i].cost);
                return ;
            }
        }
}
int main()
{
    scanf("%d%d", &n, &l);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &a[i].first, &a[i].second);
        b[++cntb] = edg(s, i, l - a[i].second);
        b[++cntb] = edg(t, i, a[i].second);
        for (int j = 1; j < i; j++)
            b[++cntb] = edg(i, j, caldis(a[i].first, a[i].second, a[j].first, a[j].second));
    }
//    cout << cntb << endl;
    solve();
    return 0;
}

2 二分

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define MAXN (500 + 5)
#define eps (0.000001)
#define DD double
#define pii pair<int, int>
const int s = 0, t = 501;
using namespace std;
int fa[MAXN], n, l;
pii a[MAXN];
void init()
{ for (int i = s; i <= t; i++)    fa[i] = i; }
int find(int x)
{ return ((x == fa[x]) ? x : (fa[x] = find(fa[x]))); }
void uni(int x, int y)
{ fa[find(x)] = find(y); }
DD caldis(int x0, int y0, int x1, int y1)
{ return sqrt((x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0)); }
bool pd(DD x)
{
    init();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i != j && caldis(a[i].first, a[i].second, a[j].first, a[j].second) < x + eps)
                uni(i, j);
    for (int i = 1; i <= n; i++)
    {
        if (l - a[i].second <= x)
            uni(s, i);
        if (a[i].second <= x)
            uni(i, t);
    }

    return !(find(s) == find(t));
}
void ef()
{
    DD le = 0, ri = 100000;
    while (ri - le >= eps)
    {
        DD mi = (le + ri) / 2;
        if (pd(mi))
            le = mi;
        else
            ri = mi;
    }
    printf("%.3f", le + 0.0005);
}
int main()
{
    scanf("%d%d", &n, &l);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &a[i].first, &a[i].second);
    ef();
    return 0;
}

By 联赛钦定爆零的 Cansult