二分爆炸半径R，判断是否可行，如果可行，半径可以继续增加。
之前建图有误，结果一直不对。
#include#include #include #include #include #include using namespace std;const int MAXN = 222;const double eps = 1e-5;struct Point{ double x, y; Point( double x = 0.0, double y = 0.0 ): x(x), y(y) { } void readPoint() { scanf( "%lf%lf", &x, &y ); return; }};struct TwoSAT{ int n; vector G[ MAXN << 1 ]; bool mark[MAXN << 1]; int S[MAXN << 1], top; bool DFS( int x ) { if ( mark[x^1] ) return false; if ( mark[x] ) return true; mark[x] = true; S[ ++top ] = x; int sz = G[x].size(); for ( int i = 0; i < sz; ++i ) if ( !DFS( G[x][i] ) ) return false; return true; } void init( int n ) { this->n = n; for ( int i = 0; i < (n*2); ++i ) G[i].clear(); memset( mark, false, sizeof(mark) ); return; } void add_clause( int x, int xval, int y, int yval ) { x = x * 2 + xval; y = y * 2 + yval; G[x^1].push_back(y); G[y^1].push_back(x); return; } bool solved() { for ( int i = 0; i < ( n * 2 ); i += 2 ) if ( !mark[i] && !mark[i + 1] ) { top = 0; if( !DFS(i) ) { while ( top > 0 ) mark[ S[top--] ] = false; if ( !DFS(i + 1) ) return false; } } return true; }};int N;Point P[MAXN][2];TwoSAT Graph;double dist[110][2][110][2];double dcmp( double a ){ if ( fabs(a) < eps ) return 0; return a < 0 ? -1 : 1;}double dis( Point a, Point b ){ return sqrt( (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y) );}bool check( double mid ){ Graph.init( N ); mid *= 2.0; for ( int i = 0; i < N; ++i ) for ( int a = 0; a < 2; ++a ) for ( int j = i + 1; j < N; ++j ) for ( int b = 0; b < 2; ++b ) { if ( dcmp( dist[i][a][j][b] - mid ) < 0 ) { Graph.add_clause( i, a ^ 1, j, b ^ 1 ); } } return Graph.solved();}int main(){ while ( scanf( "%d", &N ) == 1 ) { for ( int i = 0; i < N; ++i ) { P[i][0].readPoint(); P[i][1].readPoint(); } for ( int i = 0; i < N; ++i ) for ( int a = 0; a < 2; ++a ) for ( int j = i + 1; j < N; ++j ) for ( int b = 0; b < 2; ++b ) dist[i][a][j][b] = dist[j][b][i][a] = dis( P[i][a], P[j][b] ); double l = 0.0, r = dis( Point( -10000.0, -10000.0 ), Point( 10000.0, 10000.0 ) ); double mid, ans; while ( r - l > eps ) { mid = ( l + r ) / 2.0; if ( check(mid) ) { ans = mid; l = mid; //printf( "mid = %.2f\n", mid ); } else r = mid; } printf( "%.2f\n", ans ); } return 0;}