HDU 3622 Bomb Game(2
程序员文章站
2022-05-11 17:54:50
...
HDU 3622 Bomb Game(2-SAT二分) http://acm.hdu.edu.cn/showproblem.php?pid=3622 题意: 有N对地点,每对地点中的一个地方要放一个*,你可以控制*的爆炸半径,现在要求所有N个被放的*爆炸范围不重叠.问你在所有可行方案中的*爆炸最大半径是多少?(假
HDU 3622 Bomb Game(2-SAT+二分)
http://acm.hdu.edu.cn/showproblem.php?pid=3622
题意:
有N对地点,每对地点中的一个地方要放一个*,你可以控制*的爆炸半径,现在要求所有N个被放的*爆炸范围不重叠.问你在所有可行方案中的*爆炸最大半径是多少?(假设所有*爆炸半径相同,本假设与原提议的要求等价,可以自己想想)
分析:
直接二分可能的爆炸半径mid,然后对于mid来说,遍历任意两点的所有组合.如果a=0的点与b=1的点的距离
AC代码:
#include#include #include #include using namespace std; const int maxn=100+10; int n; struct TwoSAT { int n; vector G[maxn*2]; int S[maxn*2],c; bool mark[maxn*2]; 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 n=n; for(int i=0;i0) mark[S[--c]]=false; if(!dfs(i+1)) return false; } } return true; } }TS; struct Point { double x,y; }; struct Node { Point p[2]; }s[maxn]; double dist(int i,int vi,int j,int vj) { double x1,y1,x2,y2; x1 = s[i].p[vi].x; y1 = s[i].p[vi].y; x2 = s[j].p[vj].x; y2 = s[j].p[vj].y; return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); } bool ok(double mid) { TS.init(n); for(int i=0;i (1e-4) ) { double mid = (R+L)/2; if(ok(mid)) L=mid; else R=mid; } printf("%.2lf\n",L); } return 0; }