Bomb Game(2-SAT)

Posted on | Post modified:

HDU 3622 Bomb Game(2-SAT)

题意：

一个游戏有$n$轮，每轮提供给你两个坐标，你选择其中一个放置炸弹，到最后会放置$n$个炸弹，要保证任意两个炸弹的爆炸区域不会相交，每个炸弹的爆炸半径由你来决定，你的目的是使最小的半径最大。

题解：

考虑二分半径，对于半径$r$，$O(n^2)$的建立约束关系，利用$2-SAT$判断可行性。时间复杂度$O(n^2log(n))$。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<bits/stdc++.h>

using namespace std;
const int N = 500;
int n,m,scc,idx,color[N],low[N],dfn[N];
vector<int> G[N];
bool is_instack[N];stack<int> sta;
void init(int n){
    scc=idx=0;
    for(int i=1;i<=2*n;i++){
        low[i]=dfn[i]=is_instack[i]=color[i]=0;
        G[i].clear();
    }
    while(!sta.empty()) sta.pop();
}
void Tarjan(int u){
    low[u]=dfn[u]=++idx;
    sta.push(u);is_instack[u]=1;
    for(int v:G[u]){
        if(!dfn[v]){
            Tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(is_instack[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u]){
        ++scc;
        while(1){
            int temp=sta.top();
            color[temp]=scc;
            is_instack[temp]=0;
            sta.pop();
            if(temp==u) break;
        }
    }
}
struct Point{
    double x,y;
}p[N][2];
double dis(Point a,Point b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool check(double r){
    init(n);
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(2.0*r>dis(p[i][0],p[j][0])){
                //cout<<dis(p[i][0],p[j][0])<<endl;
                G[i].push_back(j+n);
                G[j].push_back(i+n);
            }
            if(2.0*r>dis(p[i][1],p[j][1])){
                G[i+n].push_back(j);
                G[j+n].push_back(i);
            }
            if(2.0*r>dis(p[i][0],p[j][1])){
                G[i].push_back(j);
                G[j+n].push_back(i+n);
            }
            if(2.0*r>dis(p[i][1],p[j][0])){
                G[i+n].push_back(j+n);
                G[j].push_back(i);
            }
        }
    }
    for(int i=1;i<=2*n;i++){
        if(!dfn[i]) Tarjan(i);
    }
    for(int i=1;i<=n;i++){
        if(color[i]==color[i+n]){
            return 0;
        }
    }
    return 1;
}
int main(){
    while(scanf("%d",&n)!=EOF){
        init(n);
        for(int i=1;i<=n;i++){
            scanf("%lf %lf %lf %lf",&p[i][0].x,&p[i][0].y,&p[i][1].x,&p[i][1].y);   
        }
        // cout<<check(1.41)<<endl;
        double l=0;double r=1e18;
        for(int i=1;i<=100;i++){
            double mid=(l+r)*0.5;
            if(check(mid)) l=mid;
            else r=mid;
        }
        printf("%.2lf\n",l);
    }
    return 0;
}