HDU3622BombGame(2

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;in=n;
 for(int i=0;i<2*n;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].push_back(y);
 }

 bool solve()
 {
 for(int i=0;i<2*n;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;
 }
}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;
}