首页 > 代码库 > HDU 3622 Bomb Game(二分+2SAT)
HDU 3622 Bomb Game(二分+2SAT)
题意:有一个游戏,有n个回合,每回合可以在指定的2个区域之一放炸弹,炸弹范围是一个圈,要求每回合的炸弹范围没有重合。得分是炸弹半径最小的值。求可以得到的最大分数。
思路:二分+2SAT。
二分炸弹范围,再根据有无重合建图,用2SAT判定。
#include <cstdio>#include <cmath>#include <vector>#include <cstring>using namespace std;const int maxn =105;struct TwoSAT{ int n; vector<int> G[maxn*2]; bool mark[maxn*2]; int S[maxn*2],c; bool dfs(int x) { if(mark[x^1]) return false; if(mark[x]) return true; mark[x]=true; S[c++]=x; for(int i=0; i<G[x].size(); ++i) if(!dfs(G[x][i])) return false; return true; } void init(int n) { this->n=n; for(int i=0; i<n*2; ++i) G[i].clear(); memset(mark,0,sizeof(mark)); } void add_clause(int x,int xval,int y,int yval) { x=x*2+xval; y=y*2+yval; G[x^1].push_back(y); G[y^1].push_back(x); } bool solve() { for(int i=0; i<n*2; i+=2) { if(!mark[i]&&!mark[i+1]) { c=0; if(!dfs(i)) { while(c>0) mark[S[--c]]=false; if(!dfs(i+1)) return false; } } } return true; }};struct Point{ int x,y;};Point p[105][2];int n;TwoSAT solver;double distan(Point a,Point b){ return sqrt((a.x*1.0-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}bool judge(double d){ solver.init(n); for(int i=0; i<n; ++i)for(int a=0; a<2; ++a) for(int j=i+1; j<n; ++j)for(int b=0; b<2; ++b) if(distan(p[i][a],p[j][b])<=2*d) solver.add_clause(i,a^1,j,b^1); return solver.solve();}int main(){ while(scanf("%d",&n)!=EOF) { for(int i=0; i<n; ++i) { for(int j=0; j<2; ++j) scanf("%d%d",&p[i][j].x,&p[i][j].y); } double maxi=0; solver.init(n); for(int i=0; i<n; ++i)for(int a=0; a<2; ++a) for(int j=i+1; j<n; ++j)for(int b=0; b<2; ++b) maxi=max(maxi,distan(p[i][a],p[j][b])); double L=0,R=maxi; for(int i=0; i<30; ++i) { double mid=(L+R)/2; if(judge(mid)) L=mid; else R=mid; } printf("%.2lf\n",L); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。