Bomb Game(2-SAT)

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;
}