拯救小云公主

#include <bits/stdc++.h>
using namespace std;
int n, U, D, L, R;
double row, line;
double dis[3005][3005];
double x[3005], y[3005];
int fa[3015];
int findFa(int x)
{
    if (fa[x] == x)
        return x;
    return fa[x] = findFa(fa[x]);
}
bool check(double r)
{
    for (int i = 1; i <= n + 4; i++)
        fa[i] = i;
    // 与四条边
    for (int i = 1; i <= n; i++)
    {
        if (x[i] - 1 <= r)
            fa[findFa(D)] = findFa(i);
        if (row - x[i] <= r)
            fa[findFa(U)] = findFa(i);
        if (y[i] - 1 <= r)
            fa[findFa(L)] = findFa(i);
        if (line - y[i] <= r)
            fa[findFa(R)] = findFa(i);
    }
    // BOSS 之间
    for (int i = 1; i <= n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            if (dis[i][j] <= (r * 2))
                fa[findFa(i)] = findFa(j);
        }
    }
    // 返回结果
    if ((findFa(U) == findFa(D)) ||
        (findFa(L) == findFa(R)) ||
        (findFa(L) == findFa(D)) ||
        (findFa(U) == findFa(R)))
        return false;
    return true;
}
int main()
{
    cin >> n >> row >> line;
    for (int i = 1; i <= n; i++)
        cin >> x[i] >> y[i];
    U = n + 1, D = n + 2, L = n + 3, R = n + 4;
    // 预处理距离，避免tle
    for (int i = 1; i <= n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            dis[i][j] = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
        }
    }
    double l = 0;
    double r = 1e6;
    while ((r - l) > 1e-6)
    {
        double mid = (l + r) / 2;
        if (check(mid))
            l = mid;
        else
            r = mid;
    }
    cout << fixed << setprecision(2) << l << "\n";
    return 0;
}