首页 > 代码库 > 【2-SAT】HDU3622-Bomb Game
【2-SAT】HDU3622-Bomb Game
【题目大意】
给n对炸弹可以放置的位置(每个位置为一个二维平面上的点),每次放置炸弹是时只能选择这一对中的其中一个点,每个炸弹爆炸的范围半径都一样,控制爆炸的半径使得所有的爆炸范围都不相交(可以相切),求解这个最大半径。
【思路】
显然是二分答案！二分半径，2-SAT建图部分是最裸的。
【错误点】
注意一下精度啊，HDU根本不提供所谓的±0.01..
一开始写了printf("%.2f\n",floor(ub*100)/100);
事实上写printf("%.2f\n",ub);就好啦。
1 #include<bits/stdc++.h> 2 #define eps 1e-8 3 using namespace std; 4 const int MAXN=250; 5 const int INF=0x7fffffff; 6 int n; 7 int x[MAXN],y[MAXN]; 8 int dfn[MAXN],low[MAXN],col[MAXN],instack[MAXN],colcnt,cnt; 9 vector<int> E[MAXN]; 10 stack<int> S; 11 12 void addedge(int u,int v) 13 { 14 E[u].push_back(v); 15 } 16 17 double dist(int x1,int y1,int x2,int y2) 18 { 19 double ret=sqrt((double)(x1-x2)*(x1-x2)+(double)(y1-y2)*(y1-y2)); 20 //cout<<x1<<‘ ‘<<x2<<‘ ‘<<y1<<‘ ‘<<y2<<‘ ‘<<ret<<endl; 21 return ret; 22 } 23 24 void tarjan(int u) 25 { 26 dfn[u]=low[u]=++cnt; 27 instack[u]=1; 28 S.push(u); 29 for (int i=0;i<E[u].size();i++) 30 { 31 int v=E[u][i]; 32 if (!instack[v]) 33 { 34 tarjan(v); 35 low[u]=min(low[u],low[v]); 36 37 } 38 else if (instack[v]==1) low[u]=min(low[u],dfn[v]); 39 } 40 41 if (dfn[u]==low[u]) 42 { 43 colcnt++; 44 int x; 45 do 46 { 47 x=S.top(); 48 col[x]=colcnt; 49 instack[x]=2; 50 S.pop(); 51 }while (x!=u); 52 } 53 } 54 55 void build(double r) 56 { 57 for (int i=0;i<MAXN;i++) vector<int>().swap(E[i]); 58 for (int i=1;i<=n-1;i++) 59 for (int j=i+1;j<=n;j++) 60 { 61 if (dist(x[i],y[i],x[j],y[j])<2*r) addedge(i,j+n),addedge(j,i+n); 62 if (dist(x[i],y[i],x[j+n],y[j+n])<2*r) addedge(i,j),addedge(j+n,i+n); 63 if (dist(x[i+n],y[i+n],x[j],y[j])<2*r) addedge(i+n,j+n),addedge(j,i); 64 if (dist(x[i+n],y[i+n],x[j+n],y[j+n])<2*r) addedge(i+n,j),addedge(j+n,i); 65 } 66 } 67 68 void init() 69 { 70 for (int i=1;i<=n;i++) 71 { 72 scanf("%d%d",&x[i],&y[i]); 73 scanf("%d%d",&x[i+n],&y[i+n]); 74 } 75 } 76 77 void solve() 78 { 79 double lb=0,ub=INF; 80 while (ub-lb>eps) 81 { 82 double mid=(lb+ub)/2; 83 build(mid); 84 memset(instack,0,sizeof(instack)); 85 colcnt=cnt=0; 86 for (int i=1;i<=2*n;i++) if (!instack[i]) tarjan(i); 87 int flag=1; 88 for (int i=1;i<=n;i++) 89 if (col[i]==col[i+n]) 90 { 91 flag=0; 92 break; 93 } 94 if (flag) lb=mid; 95 else ub=mid; 96 } 97 printf("%.2f\n",ub); 98 } 99 100 int main()101 {102 while (scanf("%d",&n)!=EOF)103 {104 init();105 solve();106 }107 return 0;108 }
[写随机数据上瘾了所以这次也附上]
1 #include<bits/stdc++.h> 2 3 int main() 4 { 5 freopen("test.out","w",stdout); 6 for (int i=1;i<=20;i++) 7 { 8 int n=rand()%98+2; 9 printf("%d\n",n);10 for (int j=1;j<=n;j++)11 {12 int x=rand()%2001-1000,y=rand()%2001-1000;13 printf("%d %d ",x,y);14 x=rand()%2001-1000,y=rand()%2001-1000;15 printf("%d %d\n",x,y);16 }17 }18 return 0;19 }
【2-SAT】HDU3622-Bomb Game
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。