正解2-SAT。
我用DLX想搜一搜的，结果TLE了……
没什么遗憾，最起码我尝试过了。
扔个代码留作纪念。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm> using namespace std; const int INF = << ;
const int MAXN = ;
const double eps = 1e-; struct Point
{
double x, y, z;
Point( double x = , double y = , double z = ):x(x), y(y), z(z){ }
void readPoint()
{
scanf( "%lf%lf%lf", &x, &y, &z );
return;
}
}; bool mx[MAXN][]; //01矩阵
int C[MAXN*], cnt[];
int U[MAXN*], D[MAXN*];
int L[MAXN*], R[MAXN*];
int head;
int maxr, maxc;
Point P[MAXN];
int N; int dcmp( double a )
{
if ( fabs(a) < eps ) return ;
return a < ? - : ;
} double Dis( 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 ) );
} void Remove( int c )
{
int i, j;
L[ R[c] ] = L[c];
R[ L[c] ] = R[c];
for ( i = D[c]; i != c; i = D[i] )
{
for ( j = R[i]; j != i; j = R[j] )
{
U[ D[j] ] = U[j];
D[ U[j] ] = D[j];
--cnt[ C[j] ];
}
}
return;
} void Resume( int c )
{
int i, j;
R[ L[c] ] = c;
L[ R[c] ] = c;
for ( i = D[c]; i != c; i = D[i] )
{
for ( j = R[i]; j != i; j = R[j] )
{
U[ D[j] ] = j;
D[ U[j] ] = j;
++cnt[ C[j] ];
}
}
return;
} bool DFS( int cur )
{
int i, j, c, minv; if ( cur > N ) return false;
if ( R[head] == head )
{
if ( cur == N )
return true;
return false;
} minv = INF;
for ( i = R[head]; i != head; i = R[i] )
{
if ( cnt[i] < minv )
{
minv = cnt[i];
c = i;
}
} Remove(c);
for ( i = D[c]; i != c; i = D[i] )
{
for( j = R[i]; j != i; j = R[j] )
Remove( C[j] ); if ( DFS( cur + ) ) return true; for( j = R[i]; j != i; j = R[j] )
Resume( C[j] );
} Resume(c);
return false;
} bool build()
{
int i, j, cur, pre, first;
head = ;
for ( i = ; i < maxc; ++i )
{
R[i] = i + ;
L[i + ] = i;
}
R[ maxc ] = ;
L[] = maxc; //列双向链表
for ( j = ; j <= maxc; ++j )
{
pre = j;
cnt[j] = ;
for ( i = ; i <= maxr; ++i )
{
if ( mx[i][j] )
{
++cnt[j];
cur = i * maxc + j; //当前节点的编号
C[cur] = j; //当前节点所在列
D[pre] = cur;
U[cur] = pre;
pre = cur;
}
}
U[j] = pre;
D[pre] = j;
if ( !cnt[j] ) return false; //一定无解
} //行双向链表
for ( i = ; i <= maxr; ++i )
{
pre = first = -;
for ( j = ; j <= maxc; ++j )
{
if( mx[i][j] )
{
cur = i * maxc + j;
if ( pre == - ) first = cur;
else
{
R[pre] = cur;
L[cur] = pre;
}
pre = cur;
}
}
if ( first != - )
{
R[pre] = first;
L[first] = pre;
}
}
return true;
} /**************以上DLX模板*****************/ void show()
{
for ( int i = ; i <= maxr; ++i )
{
for ( int j = ; j <= maxc; ++j )
printf( "%d", mx[i][j] );
puts("");
}
puts("---------");
return;
} //得到该情况下的01矩阵
void init( double R )
{
memset( mx, false, sizeof(mx) ); for ( int i = ; i <= maxr; ++i )
{
mx[i][i] = true;
if ( i % )
{
//printf("ii %d %d\n", i, i + 1);
mx[i][N + N + i/+] = true;
mx[i + ][N + N + i/+] = true;
}
for ( int j = ; j <= maxr; ++j )
{
//printf("i=%d j=%d\n", i, j );
if ( dcmp( Dis( P[i], P[j] ) - 2.0 * R ) < )
mx[j][i] = true;
}
}
//show();
return;
} bool ok( double mid )
{
init( mid );
if ( build() == false ) return false;
if ( DFS( ) == false ) return false;
return true;
} double solved()
{
double l = ;
double r = Dis( Point(, , ), Point( , , ) );
double ans;
while ( dcmp( r - l ) > )
{
double mid = ( l + r ) / 2.0;
//printf( "mid = %.6f\n", mid );
if ( ok( mid ) )
{
l = mid;
ans = mid;
}
else r = mid;
}
return ans;
} int main()
{
//freopen( "in.txt", "r", stdin );
//freopen( "out.txt", "w", stdout );
while ( scanf( "%d", &N ) == )
{
maxr = ;
for ( int i = ; i < N; ++i )
{
P[++maxr].readPoint();
P[++maxr].readPoint();
}
maxc = maxr + N;
double ans=(int)(solved()*+0.5+eps)/1000.0;
if ( !ok(ans) ) ans -= 0.001;
printf( "%.3f\n", ans );
}
return ;
}