#pragma warning(disable:4996)
#include
#include
#include
#include
#include
#define ll long long
#define maxn 220
#define eps 1e-8
using
namespace std;
struct
Point
class="line number14 index13 alt1">{
double
x, y, z;
Point(double
xi, double
yi, double
zi) :x(xi), y(yi), z(zi){}
Point(){}
}p[maxn * 2];
double
dist(Point a, Point b){
return
sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y) + (a.z - b.z)*(a.z - b.z));
class="line number22 index21 alt1">}
double
dis[maxn * 2][maxn * 2];
int
low[maxn * 2];
int
pre[maxn * 2];
int
dfs_clock;
int
sta[maxn * 2];
int
st;
int
sccno[maxn * 2];
int
n;
vector<int> G[maxn * 2];
int
scc_cnt;
int
dcmp(double
x){
return
(x > eps) - (x <-eps);
class="line number38 index37 alt1">}
void
dfs(int
u){
low[u] = pre[u] = ++dfs_clock;
sta[++st] = u;
for
(int i = 0; i
int
v = G[u][i];
if
(!pre[v]){
dfs(v);
low[u] = min(low[u], low[v]);
}
else
if (!sccno[v]){
low[u] = min(low[u], pre[v]);
}
}
if
(low[u] == pre[u]){
++scc_cnt;
while
(1){
int
x = sta[st]; st--;
sccno[x] = scc_cnt;
if
(x == u) break;
}
}
class="line number61 index60 alt2">}
bool
judge(double
x)
class="line number64 index63 alt1">{
memset(sccno, 0, sizeof(sccno));
memset(pre, 0, sizeof(pre));
memset(low, 0, sizeof(low));
st = 0; dfs_clock = 0;
scc_cnt = 0;
for
(int i = 0; i <= 2 * n; i++) G[i].clear();
for
(int i = 0; i
for
(int j = i + 1; j
if
(dcmp(dis[i][j] - 2 * x) <0){
G[i].push_back(j + n);
G[j].push_back(i + n);
}
if
(dcmp(dis[i][j + n] - 2 * x) <0){
G[i].push_back(j);
G[j + n].push_back(i + n);
}
if
(dcmp(dis[i + n][j] - 2 * x) <0){
G[i + n].push_back(j + n);
G[j].push_back(i);
}
if
(dcmp(dis[i + n][j + n] - 2 * x) <0){
G[i + n].push_back(j);
G[j + n].push_back(i);
}
}
}
for
(int i = 0; i <2 * n; i++){
if
(!pre[i]) dfs(i);
}
for
(int i = 0; i
if
(sccno[i] == sccno[i + n]) return
false;
}
return
true;
class="line number99 index98 alt2">}
int
main()
class="line number102 index101 alt1">{
while
(cin >> n)
{
for
(int i = 0; i
scanf("%lf%lf%lf", &p[i].x, &p[i].y, &p[i].z);
scanf("%lf%lf%lf", &p[i + n].x, &p[i + n].y, &p[i + n].z);
}
for
(int i = 0; i <2 * n; i++){
for
(int j = i + 1; j <2 * n; j++){
dis[i][j] = dis[j][i] = dist(p[i], p[j]);
}
}
double
l = 0, r = 1e10;
while
(dcmp(r - l)>0){
double
mid = (l + r) / 2;
if
(judge(mid)) l = mid;
else
r = mid;
}
int
tmp = l * 1000;
double
ans = tmp / 1000.0;
printf("%.3lf\n", ans);
}
return
0;
class="line number125 index124 alt2">}
![扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]](https://img.php1.cn/3c972/245b5/42f/19446f78530d3747.jpeg)
京公网安备 11010802041100号