【题目大意】
给n对炸弹可以放置的位置(每个位置为一个二维平面上的点),每次放置炸弹是时只能选择这一对中的其中一个点,每个炸弹爆炸的范围半径都一样,控制爆炸的半径使得所有的爆炸范围都不相交(可以相切),求解这个最大半径。
【思路】
显然是二分答案！二分半径，2-SAT建图部分是最裸的。
【错误点】
注意一下精度啊，HDU根本不提供所谓的±0.01..
一开始写了printf("%.2f\n",floor(ub*100)/100);
事实上写printf("%.2f\n",ub);就好啦。
#include<bits/stdc++.h>
#define eps 1e-8
using namespace std;
const int MAXN=;
const int INF=0x7fffffff;
int n;
int x[MAXN],y[MAXN];
int dfn[MAXN],low[MAXN],col[MAXN],instack[MAXN],colcnt,cnt;
vector<int> E[MAXN];
stack<int> S; void addedge(int u,int v)
{
E[u].push_back(v);
} double dist(int x1,int y1,int x2,int y2)
{
double ret=sqrt((double)(x1-x2)*(x1-x2)+(double)(y1-y2)*(y1-y2));
//cout<<x1<<' '<<x2<<' '<<y1<<' '<<y2<<' '<<ret<<endl;
return ret;
} void tarjan(int u)
{
dfn[u]=low[u]=++cnt;
instack[u]=;
S.push(u);
for (int i=;i<E[u].size();i++)
{
int v=E[u][i];
if (!instack[v])
{
tarjan(v);
low[u]=min(low[u],low[v]); }
else if (instack[v]==) low[u]=min(low[u],dfn[v]);
} if (dfn[u]==low[u])
{
colcnt++;
int x;
do
{
x=S.top();
col[x]=colcnt;
instack[x]=;
S.pop();
}while (x!=u);
}
} void build(double r)
{
for (int i=;i<MAXN;i++) vector<int>().swap(E[i]);
for (int i=;i<=n-;i++)
for (int j=i+;j<=n;j++)
{
if (dist(x[i],y[i],x[j],y[j])<*r) addedge(i,j+n),addedge(j,i+n);
if (dist(x[i],y[i],x[j+n],y[j+n])<*r) addedge(i,j),addedge(j+n,i+n);
if (dist(x[i+n],y[i+n],x[j],y[j])<*r) addedge(i+n,j+n),addedge(j,i);
if (dist(x[i+n],y[i+n],x[j+n],y[j+n])<*r) addedge(i+n,j),addedge(j+n,i);
}
} void init()
{
for (int i=;i<=n;i++)
{
scanf("%d%d",&x[i],&y[i]);
scanf("%d%d",&x[i+n],&y[i+n]);
}
} void solve()
{
double lb=,ub=INF;
while (ub-lb>eps)
{
double mid=(lb+ub)/;
build(mid);
memset(instack,,sizeof(instack));
colcnt=cnt=;
for (int i=;i<=*n;i++) if (!instack[i]) tarjan(i);
int flag=;
for (int i=;i<=n;i++)
if (col[i]==col[i+n])
{
flag=;
break;
}
if (flag) lb=mid;
else ub=mid;
}
printf("%.2f\n",ub);
} int main()
{
while (scanf("%d",&n)!=EOF)
{
init();
solve();
}
return ;
}
[写随机数据上瘾了所以这次也附上]
#include<bits/stdc++.h> int main()
{
freopen("test.out","w",stdout);
for (int i=;i<=;i++)
{
int n=rand()%+;
printf("%d\n",n);
for (int j=;j<=n;j++)
{
int x=rand()%-,y=rand()%-;
printf("%d %d ",x,y);
x=rand()%-,y=rand()%-;
printf("%d %d\n",x,y);
}
}
return ;
}