博主的 BiBi 时间

感觉自己天天 BiBi 好累。。。（这种事情不是可以让它停止了吗滑稽）

Solution

这是比较典型的 \(\mathtt{2-SAT}\) 问题。

我们可以做一个二分，枚举最小半径。然后连边就是如果两个点的距离小于 \(2*r\) 就连。

重要的是这道题有个坑：可能有不连边的情况。这种情况肯定是可以的，但是如果贸然进入 \(\mathtt{dfs}\)，再修改一些奇奇怪怪的值，就会有大问题。（比如后面 \(belong\) 数组的比较）最好特判掉。

Code

#include 
#include 
#include 

const double eps = 1e-5;
const int N = 205;

int n, len, head[N], Head[N], scc[N], tot, cnt, to[N * N * 4], nxt[N * N * 4], be[N], x[N], y[N];
bool vis[N];

int read() {
    int x = 0, f = 1; char s;
    while((s = getchar()) > '9' || s < '0') if(s == '-') f = -1;
    while(s >= '0' && s <= '9') x = (x << 1) + (x << 3) + (s ^ 48), s = getchar();
    return x * f;
}

void addEdge(const int u, const int v) {
    to[++ cnt] = v, nxt[cnt] = head[u], head[u] = cnt;
    to[++ cnt] = u, nxt[cnt] = Head[v], Head[v] = cnt;
}

void dfs1(const int u) {
    vis[u] = 1;
    for(int i = head[u]; i; i = nxt[i])
        if(! vis[to[i]]) dfs1(to[i]);
    scc[++ tot] = u;
}

void dfs2(const int u) {
    vis[u] = 1; be[u] = tot;
    for(int i = Head[u]; i; i = nxt[i])
        if(! vis[to[i]]) dfs2(to[i]);
}

bool check(const double goal) {
    memset(head, 0, sizeof head); memset(Head, 0, sizeof Head); cnt = 0;
    for(int i = 0; i < n; ++ i)
        for(int j = i + 1; j < n; ++ j)
            if(sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])) < goal * 2)
                addEdge(i, j ^ 1), addEdge(j, i ^ 1);
    if(! cnt) return 1;
    memset(vis, 0, sizeof vis); tot = 0;
    for(int i = 0; i < n; ++ i) if(! vis[i]) dfs1(i);
    memset(vis, 0, sizeof vis); tot = 0;
    for(int i = n - 1; ~i; -- i)
        if(! vis[scc[i]]) ++ tot, dfs2(scc[i]);
    for(int i = 0; i < n; ++ i) if(be[i] == be[i ^ 1]) return 0;
    return 1;
}

int main() {
    double l, r, mid, ans;
    while(~ scanf("%d", &n)) {
        len = -1;
        for(int i = 1; i <= n; ++ i) x[++ len] = read(), y[len] = read(), x[++ len] = read(), y[len] = read();
        n <<= 1;
        l = 0; r = 20000;
        while(r - l > eps) {
            mid = (l + r) / 2;
            if(check(mid)) l = mid, ans = mid;
            else r = mid;
        }
        printf("%.2f\n", mid);
    }
    return 0;
}