HDU3622 Bomb Game(二分+2-SAT)

题意

给n对炸弹可以放置的位置(每个位置为一个二维平面上的点),

每次放置炸弹是时只能选择这一对中的其中一个点,每个炸弹爆炸

的范围半径都一样,控制爆炸的半径使得所有的爆炸范围都不相

交(可以相切),求解这个最大半径.

题解

首先二分最大半径值,然后2-sat构图判断其可行性,
对于每 两队位置(u,uu)和(v,vv),如果u和v之间的距离小于2*id,
也就是说位置u和位置v处不能同时防止炸弹(两范围相交),
所以连边(u,vv) 和(v,uu),求解强连通分量判断可行性. 
注意精度问题

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

#define debug(x) cout << "fuck bug " << x << "\n";

#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

const int maxn = 4e4 + ;

const double eps = 0.00000001;

typedef long long ll;

int n,m;

struct edge

{

    int to,nxt;

}e[maxn];//,eg[maxn];

int head[maxn],tot;//int head2[maxn],tot2;

void add(int u ,int v){

    e[++tot].to = v;

    e[tot].nxt = head[u];

    head[u] = tot;

    // eg[++tot2].to = v;

    // eg[tot2].nxt = head2[u];

    // head2[u] = tot2;

}

int dfn[maxn],low[maxn],num,inStack[maxn];

int stack[maxn],top,cnt,C[maxn];

void tarjan(int x) {

    dfn[x] = low[x] = ++num;

    stack[++top] = x; inStack[x] = true;

    for (int i = head[x]; i; i = e[i].nxt) {

        int y = e[i].to;

        if (dfn[y] == ) {

            tarjan(y);

            low[x] = min(low[x], low[y]);

        } else if (inStack[y]) {

            low[x] = min(low[x], low[y]);

        }

    }

    if (low[x] == dfn[x]) {

        cnt++;

        int z;

        do {

            z = stack[top--];

            inStack[z] = false;

            C[z] = cnt;

        } while (z != x);

    }

}

struct Point

{

    double x,y;

}P[maxn];

double dis(Point a,Point b){

    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

}

void init(){

    memset(head,,sizeof head);

    memset(e,,sizeof e);

    //memset(head2,0,sizeof head2);

    memset(dfn,,sizeof dfn);

    //memset(vis2,0,sizeof vis2);

    //tot2 = tot = 0;

    //cnt1 = cnt = 0;

    tot = top = cnt = num =  ;

    memset(C,,sizeof C);

}

int main(int argc, char const *argv[])

{

    int n;

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

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

            scanf("%lf %lf %lf %lf",&P[i].x,&P[i].y,&P[i^].x,&P[i^].y);

        }

        double l = ,r = ;

        double ans = -;

        while(r - l > eps){

            double mid = (l + r) / ;

            init();

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

                for(int j = i + ;j < n + n;j ++){

                    if(dis(P[i],P[j]) <  * mid){

                        add(i,j^);

                        add(j,i^);

                    }

                }

            }

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

                for(int j = i + ;j < n + n;j ++){

                    if(dis(P[i],P[j]) <  * mid){

                        add(i,j^);

                        add(j,i^);

                    }

                }

            }

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

                if(!dfn[i]) tarjan(i);

            }

            bool flag = ;

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

                if(C[i] == C[i + ]){

                    flag = ;

                    break;

                }

            }

            if(flag){

                l = mid;

                ans = mid;

            }else{

                r = mid;

            }

        }

        printf("%.2lf\n",ans);

    }

    return ;

}

巴特西

HDU3622 Bomb Game(二分+2-SAT)

题意

题解

最新文章

热门文章