hdu3622

hdu3622

题意

每回合给定两个坐标点，可以选择一个放置炸弹，自己决定炸弹的半径，问 n 个回合后，使炸弹半径最小值最大。

分析

存在对立关系：每回合只能选择一个地方放置炸弹。i 表示 第一个位置 i + n 表示第二个位置。

当 i 、j 存在交点时，i -> j + n，j -> i + n 。

code

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<vector>

#include<cmath>

using namespace std;

typedef long long ll;

const int INF = 1e9;

const int MAXN = 3e3 + 5;

int vis[MAXN], flag[MAXN];

vector<int> G[MAXN], rG[MAXN];

vector<int> vs;

int n, m;

void addedge(int x, int y)

{

    G[x].push_back(y);

    rG[y].push_back(x);

}

void dfs(int u)

{

    vis[u] = 1;

    for(int i = 0; i < G[u].size(); i++)

    {

        int v = G[u][i];

        if(!vis[v]) dfs(v);

    }

    vs.push_back(u);

}

void rdfs(int u, int k)

{

    vis[u] = 1; flag[u] = k;

    for(int i = 0; i < rG[u].size(); i++)

    {

        int v = rG[u][i];

        if(!vis[v]) rdfs(v, k);

    }

}

int scc()

{

    vs.clear();

    memset(vis, 0, sizeof vis);

    for(int i = 0; i < n; i++)

        if(!vis[i]) dfs(i);

    memset(vis, 0, sizeof vis);

    int k = 0;

    for(int i = vs.size() - 1; i >= 0; i--)

        if(!vis[vs[i]]) rdfs(vs[i], k++);

    return k;

}

bool judge()

{

    int N = n;

    n = 2 * n;

    scc();

    n /= 2;

    for(int i = 0; i < n; i++)

        if(flag[i] == flag[i + N]) return false;

    return true;

}

int x1[MAXN], y1[MAXN], x2[MAXN], y2[MAXN];

int dis2(int xi, int yi, int xj, int yj)

{

    return (xi - xj) * (xi - xj) + (yi - yj) * (yi - yj);

}

void solve()

{

    int l = 0, r = 400000005, mid;

    while(l + 1 < r)

    {

        mid = (l + r) / 2;

        for(int i = 0; i < 2 * n ;i++)

        {

            G[i].clear(); rG[i].clear();

        }

        for(int i = 0; i < n; i++)

        {

            for(int j = 0; j < i; j++)

            {

                if(dis2(x1[i], y1[i], x1[j], y1[j]) < mid)

                {

                    addedge(i, j + n);

                    addedge(j, i + n);

                }

                if(dis2(x1[i], y1[i], x2[j], y2[j]) < mid)

                {

                    addedge(i, j);

                    addedge(j + n, i + n);

                }

                if(dis2(x2[i], y2[i], x1[j], y1[j]) < mid)

                {

                    addedge(i + n, j + n);

                    addedge(j, i);

                }

                if(dis2(x2[i], y2[i], x2[j], y2[j]) < mid)

                {

                    addedge(i + n, j);

                    addedge(j + n, i);

                }

            }

        }

        if(judge()) l = mid;

        else r = mid;

    }

    printf("%.2f\n", sqrt(l) / 2.0);

}

int main()

{

    while(~scanf("%d", &n))

    {

        for(int i = 0; i < n; i++)

        {

            scanf("%d%d%d%d", &x1[i], &y1[i], &x2[i], &y2[i]);

        }

        solve();

    }

    return 0;

}