「HDU3622」Bomb Game

题意：

给 $n$ 对平面上的点，你可以在每对点中选择一个放置炸弹（不能同时都放），炸弹爆炸后所摧毁的区域是一个圆，且每个炸弹的摧毁区域的半径都一样。当然作为游戏者，你可以控制这个半径的大小。现在请你确定这个半径的最大值，使得放完 $n$ 个炸弹后，没有任何两个炸弹有重合的部分（注意相接不算相交）。

一道很典型的 2-SAT 问题。

由于不确定半径所以要二分。

2-SAT 的难点在于怎么建图，后面就是简单的 tarjan 求强连通分量判断是不是在一个强连通分量里即可，那么这道题到底怎么建图呢？

我们假设有 $2$ 个点对，分别为 $[(x_{i _1},y _{i _1}),(x _{i _2},y _{i _2})],[(x _{j _1},y _{j _1}),(x _{j _2},y _{j _2})]$ ，在图中我们用编号 $[i,i+n],[j,j+n]$ 来表示。

假设半径为 $r$ ，那么两个点 $a$ 和 $b$ 之间应满足这个条件：

dis(a,b)\ge 2\times r

那么我们分四种情况讨论这两个点对：

假如 $(x _{i _1},y _{i _1})[i]$ 和 $(x _{j _1},y _{j _1})[j]$ 不满足上面那个条件，那么选了 $i$ 就必选 $j+n$ ，选了 $j$ 就必选 $i+n$ ，连边即可。
```
if(dis(a[i],a[j])+eps<2*r)
{
	add(i,j+n);
	add(j,i+n);
}
```
同理，假如 $(x _{i _1},y _{i _1})[i]$ 和 $(x _{j _2},y _{j _2})[j+n]$ 不满足上面那个条件,那么选了 $i$ 就必选 $j$ ，选了 $j+n$ 就必选 $i+n$ 。
```
if(dis(a[i],b[j])+eps<2*r)
{
	add(i,j);
	add(j+n,i+n);
}
```
假如 $(x _{i _2},y _{i _2})[i+n]$ 和 $(x _{j _1},y _{j _1})[j]$ 不满足上面那个条件,那么选了 $i+n$ 就必选 $j+n$ ，选了 $j$ 就必选 $i$ 。
```
if(dis(b[i],a[j])+eps<2*r)
{
	add(i+n,j+n);
	add(j,i);
}
```
假如 $(x _{i _2},y _{i _2})[i+n]$ 和 $(x _{j _2},y _{j _2})[j+n]$ 不满足上面那个条件,那么选了 $i+n$ 就必选 $j$ ，选了 $j+n$ 就必选 $i$ 。
```
if(dis(b[i],b[j])+eps<2*r)
{
	add(i+n,j);
	add(j+n,i);
}
```

然后二分 $r$ ，每次重新建边判断是否有解就行了。

需要注意的是，下面这份代码会被卡，正解就是把邻接表建图换成 vector 建图，因为 vector 所占的空间会小一点，导致清空数组时会快很多，就可以不用时间超限。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=20101,maxm=2010010;
const double eps=1e-4;
double ans;
int n,num,Index;
int head[maxm],cnt;
int dfn[maxn],low[maxn];
int vis[maxn],color[maxn];
int stack[maxn],top;
int read()
{
    int n=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){n=n*10+ch-'0';ch=getchar();}
    return f*n;
}
struct point
{
	int x;
	int y;
}a[maxn],b[maxn];
struct node
{
	int next;
	int to;
}e[maxm];
inline void add(int from,int to)
{
	e[++cnt].next=head[from];
	e[cnt].to=to;
	head[from]=cnt;
}
inline void tarjan(int u)
{
	dfn[u]=low[u]=++Index;
	vis[u]=1;
	stack[++top]=u;
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(vis[v])
			low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u])
	{
		int v;
		num++;
		do
		{
			v=stack[top--];
			vis[v]=0;
			color[v]=num;
		}while(v!=u);
	}
}
inline double dis(point a,point b)
{
	return sqrt(1.0*(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
inline void clear()
{
	for(int i=0;i<=top;++i)
		stack[i]=0;
	num=cnt=Index=top=0;
	memset(e,0,sizeof(e));
	for(int i=0;i<=2*n;++i)
		dfn[i]=low[i]=vis[i]=color[i]=0;
	memset(head,0,sizeof(head));
}
inline void build(double r)
{
	for(int i=1;i<=n;++i)
		for(int j=i+1;j<=n;++j)//2个点对：ai,aj,bi,bj分别对应i,j,i+n,j+n
		{
			if(dis(a[i],a[j])+eps<2*r)
			{
				add(i,j+n);
				add(j,i+n);
			}
			if(dis(a[i],b[j])+eps<2*r)
			{
				add(i,j);
				add(j+n,i+n);
			}
			if(dis(b[i],a[j])+eps<2*r)
			{
				add(i+n,j+n);
				add(j,i);
			}
			if(dis(b[i],b[j])+eps<2*r)
			{
				add(i+n,j);
				add(j+n,i);
			}
		}
}
inline bool check()
{
	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 false;
	return true;
}
int main()
{
	n=read();
	for(int i=1;i<=n;++i)
	{
		a[i].x=read();
		a[i].y=read();
		b[i].x=read();
		b[i].y=read();
	}
	double l=0,r=20001;
	while(r-l>eps)
	{
		double mid=(l+r)/2;
		clear();
		build(mid);
		if(check())
		{
			ans=max(ans,mid);
			l=mid;
		}
		else
			r=mid;
	}
	printf("%.2lf",ans);
	return 0;
}