team2012-E1-mysol-0014
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
/* 解题报告 //
N 组气球，每组两个，都固定在空间中给定的位置上
求最大的半径 R，使得每组气球中各选出一个，分别充气到半径恰好为 R
并且这些选出的气球两两之间都不会产生重叠
显然，在看到『每组两个，各选一个』，并根据半径 R 的不同
存在着一些单向的制约条件时，就会想到经典的 2-SAT 问题
做法便是二分枚举半径 R，如果在这个半径下
某两个气球 A 和 B 之间的距离小于 2 * R，则建立 A 到 B' 及 B 到 A' 的边
其中 A' 是 A 的同组异色的气球，B' 是 B 的同组异色的气球
这种建边方式意味着，由于 A 和 B 冲突了：
1. 如果选了气球 A，就一定要选气球 B'（因为 B 不能选）
2. 如果选了气球 B，就一定要选气球 A'（因为 A 不能选）
建立好这个有向图之后，判断是否存在任意的 A 和 A' 之间存在双向路径
即，如果选了 A 就一定要选 A'，且如果选了 A' 就一定要选 A
想要判断是否出现这样的矛盾情况，方法是强联通缩点（因为速度比较快）
// By 猛犸也钻地 @ 2012.07.21 */
}}}
{{{
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
class GabowSCC{
public:
static const int SIZE = 400;
int cnt,idx[SIZE];
int gao(int n, const vector<int> e[]){
Pc=Qc=-1;
for(int i=cnt=0;i<n;i++) idx[i]=tag[i]=-1;
for(int i=use=0;i<n;i++) if(tag[i]<0) dfs(i,e);
return cnt;
}
private:
int tag[SIZE],P[SIZE],Q[SIZE],use,Pc,Qc;
void dfs(int x, const vector<int> e[]){
tag[P[++Pc]=Q[++Qc]=x]=use++;
for(size_t i=0;i<e[x].size();i++){
int y=e[x][i];
if(~idx[y]) continue;
if(~tag[y]) while(tag[y]<tag[Q[Qc]]) Qc--;
else dfs(y,e);
}
if(Q[Qc]==x) Qc--; else return;
do idx[P[Pc]]=cnt; while(P[Pc--]!=x);
cnt++;
}
}scc;
vector<int> e[400];
double l[400][400];
int main(){
int n,x[400],y[400],z[400];
while(scanf("%d",&n)==1){
n*=2;
for(int i=0;i<n;i++){
scanf("%d%d%d",x+i,y+i,z+i);
for(int j=0;j<i;j++){
int dx=x[i]-x[j];
int dy=y[i]-y[j];
int dz=z[i]-z[j];
l[i][j]=sqrt(dx*dx+dy*dy+dz*dz);
}
}
double lo=0,hi=30000;
for(int c=1;c<=80;c++){
double r=(lo+hi)/2;
bool ok=true;
for(int i=0;i<n;i++) e[i].clear();
for(int i=0;i<n;i++) for(int j=0;j<i;j++){
if(l[i][j]>=2*r || i>>1==j>>1) continue;
e[i].push_back(j^1);
e[j].push_back(i^1);
}
scc.gao(n,e);
for(int i=0;i<n;i+=2) ok&=(scc.idx[i]!=scc.idx[i+1]);
if(!ok) hi=r; else lo=r;
}
int ans=int(lo*1000+1e-8);
printf("%d.%03d\n",ans/1000,ans%1000);
}
}
}}}/* 解题报告 //
N 组气球，每组两个，都固定在空间中给定的位置上
求最大的半径 R，使得每组气球中各选出一个，分别充气到半径恰好为 R
并且这些选出的气球两两之间都不会产生重叠
显然，在看到『每组两个，各选一个』，并根据半径 R 的不同
存在着一些单向的制约条件时，就会想到经典的 2-SAT 问题
做法便是二分枚举半径 R，如果在这个半径下
某两个气球 A 和 B 之间的距离小于 2 * R，则建立 A 到 B' 及 B 到 A' 的边
其中 A' 是 A 的同组异色的气球，B' 是 B 的同组异色的气球
这种建边方式意味着，由于 A 和 B 冲突了：
1. 如果选了气球 A，就一定要选气球 B'（因为 B 不能选）
2. 如果选了气球 B，就一定要选气球 A'（因为 A 不能选）
建立好这个有向图之后，判断是否存在任意的 A 和 A' 之间存在双向路径
即，如果选了 A 就一定要选 A'，且如果选了 A' 就一定要选 A
想要判断是否出现这样的矛盾情况，方法是强联通缩点（因为速度比较快）
// By 猛犸也钻地 @ 2012.07.21 */
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
class GabowSCC{
public:
static const int SIZE = 400;
int cnt,idx[SIZE];
int gao(int n, const vector<int> e[]){
Pc=Qc=-1;
for(int i=cnt=0;i<n;i++) idx[i]=tag[i]=-1;
for(int i=use=0;i<n;i++) if(tag[i]<0) dfs(i,e);
return cnt;
}
private:
int tag[SIZE],P[SIZE],Q[SIZE],use,Pc,Qc;
void dfs(int x, const vector<int> e[]){
tag[P[++Pc]=Q[++Qc]=x]=use++;
for(size_t i=0;i<e[x].size();i++){
int y=e[x][i];
if(~idx[y]) continue;
if(~tag[y]) while(tag[y]<tag[Q[Qc]]) Qc--;
else dfs(y,e);
}
if(Q[Qc]==x) Qc--; else return;
do idx[P[Pc]]=cnt; while(P[Pc--]!=x);
cnt++;
}
}scc;
vector<int> e[400];
double l[400][400];
int main(){
int n,x[400],y[400],z[400];
while(scanf("%d",&n)==1){
n*=2;
for(int i=0;i<n;i++){
scanf("%d%d%d",x+i,y+i,z+i);
for(int j=0;j<i;j++){
int dx=x[i]-x[j];
int dy=y[i]-y[j];
int dz=z[i]-z[j];
l[i][j]=sqrt(dx*dx+dy*dy+dz*dz);
}
}
double lo=0,hi=30000;
for(int c=1;c<=80;c++){
double r=(lo+hi)/2;
bool ok=true;
for(int i=0;i<n;i++) e[i].clear();
for(int i=0;i<n;i++) for(int j=0;j<i;j++){
if(l[i][j]>=2*r || i>>1==j>>1) continue;
e[i].push_back(j^1);
e[j].push_back(i^1);
}
scc.gao(n,e);
for(int i=0;i<n;i+=2) ok&=(scc.idx[i]!=scc.idx[i+1]);
if(!ok) hi=r; else lo=r;
}
int ans=int(lo*1000+1e-8);
printf("%d.%03d\n",ans/1000,ans%1000);
}
}