Yuki 96 圏外です。( Union Find, Bucket, Furthest Pair, Convex Hull )
題意：
兩個人各拿著一台無線電要通話，無線電之間最遠可通話距離為 1 km，基地台之間則是 10 km，無線電與基地台之間則是 1 km。在兩人可通話的前提下求最大可能的歐幾里德距離。
資料規模：
基地台數量 0≤N≤120000
基地台座標 −10000≤Xi,Yi≤10000, 且為整數
保證無重複的點
時限 5000 ms
記憶體 512 MB
解法：
考慮資料規模若小一點應該要怎麼做。發現希望將可通話的基地台合成一團，使團與團之間任意點不能溝通，因為若能溝通，則兩團所有點都能溝通。若能達到這裡，就只剩下分別考慮每團的最遠距離。分團的過程暴力是 O( N ^ 2 )，乍看不能優化，但考慮分塊，將 10 * 10 的座標都作為一塊先各自合併看看之後，每一塊裡的任一點只需要考慮八方向的塊，而根據鴿籠原理，每塊至多只會有 100 個基地台，因此最差情況每個點只會和本身的塊以外的基地台合併 800 次，可以在時限內通過。最後求團中最遠點對的部分，可以先求凸包，再利用凸包上最遠距離點對的單調性質，以尺取法線性時間完成。
時間 / 空間複雜度：
O( N lg N ) / O( N )
int N; vi X, Y; void init(){ cin >> N; X = Y = vi( N ); for( int i = 0; i < N; ++i ) cin >> X[ i ] >> Y[ i ]; } struct dsu{ vi fa; dsu( int sz ){ fa = vi( sz ); for( int i = 0; i < sz; ++i ) fa[ i ] = i; } int find( int x ){ return fa[ x ] == x ? x : fa[ x ] = find( fa[ x ] ); } int merge( int a, int b ){ int x = find( a ); int y = find( b ); if( x == y ) return 0; fa[ x ] = y; return 1; } }; map< int, vi > group; int eu_dis2( int a, int b, int x, int y ){ int dx = a - x; int dy = b - y; return dx * dx + dy * dy; } double eu_dis( int a, int b, int x, int y ){ double dx = a - x; double dy = b - y; return sqrt( dx * dx + dy * dy ); } void preprocess(){ map< pii, vi > box; for( int i = 0; i < N; ++i ) box[ make_pair( ( X[ i ] + 10000 ) /10, ( Y[ i ] + 10000 ) / 10 ) ].emplace_back( i ); dsu *uf = new dsu( N ); for( auto it = box.begin(); it != box.end(); ++it ){ for( int i = 0; i < ( it->second ).size(); ++i ) for( int j = i + 1; j < ( it->second ).size(); ++j ) if( eu_dis2( X[ ( it->second )[ i ] ], Y[ ( it->second )[ i ] ], X[ ( it->second )[ j ] ], Y[ ( it->second )[ j ] ] ) <= 100 ) uf->merge( ( it->second )[ i ], ( it->second )[ j ] ); static const int dx[] = { 0, 1, 0, -1, 1, 1, -1, -1 }; static const int dy[] = { 1, 0, -1, 0, 1, -1, 1, -1 }; for( int di = 0; di < 8; ++di ){ pii key = make_pair( ( it->first ).first + dx[ di ], ( it->first ).second + dy[ di ] ); if( not box.count( key ) ) continue; auto &cur = it->second; auto &adj = box[ key ]; for( auto &u : cur ) for( auto &v : adj ) if( eu_dis2( X[ u ], Y[ u ], X[ v ], Y[ v ] ) <= 100 ) uf->merge( u, v ); } } for( int i = 0; i < N; ++i ) group[ uf->find( i ) ].emplace_back( i ); } void solve(){ double ans = N == 0 ? 1.0 : 2.0; for( auto it = group.begin(); it != group.end(); ++it ){ sort( ( it->second ).begin(), ( it->second ).end(), [ & ]( int i, int j ){ return X[ i ] != X[ j ] ? X[ i ] < X[ j ] : Y[ i ] < Y[ j ]; } ); vector< int > stk; function< double ( double, double, double, double ) > cross = [ & ]( double x1, double y1, double x2, double y2 ){ return x1 * y2 - y1 * x2; }; for( int i = 0; i < ( it->second ).size(); ++i ){ while( stk.size() >= 2 ){ int s = stk.size(); double dx1 = X[ stk[ s - 1 ] ] - X[ stk[ s - 2 ] ]; double dy1 = Y[ stk[ s - 1 ] ] - Y[ stk[ s - 2 ] ]; double dx2 = X[ ( it->second )[ i ] ] - X[ stk[ s - 2 ] ]; double dy2 = Y[ ( it->second )[ i ] ] - Y[ stk[ s - 2 ] ]; if( cross( dx1, dy1, dx2, dy2 ) <= 0.0 ) stk.pop_back(); else break; } stk.emplace_back( ( it->second )[ i ] ); } int h = stk.size(); for( int i = ( int ) ( it->second ).size() - 2; i >= 0; --i ){ while( stk.size() > h ){ int s = stk.size(); double dx1 = X[ stk[ s - 1 ] ] - X[ stk[ s - 2 ] ]; double dy1 = Y[ stk[ s - 1 ] ] - Y[ stk[ s - 2 ] ]; double dx2 = X[ ( it->second )[ i ] ] - X[ stk[ s - 2 ] ]; double dy2 = Y[ ( it->second )[ i ] ] - Y[ stk[ s - 2 ] ]; if( cross( dx1, dy1, dx2, dy2 ) <= 0.0 ) stk.pop_back(); else break; } stk.emplace_back( ( it->second )[ i ] ); } stk.pop_back(); // start h = stk.size(); for( int i = 0; i < h; ++i ) stk.emplace_back( stk[ i ] ); for( int i = 0, j = 1; i < h; ++i ){ while( eu_dis2( X[ stk[ i ] ], Y[ stk[ i ] ], X[ stk[ j ] ], Y[ stk[ j ] ] ) <= eu_dis2( X[ stk[ i ] ], Y[ stk[ i ] ], X[ stk[ j + 1 ] ], Y[ stk[ j + 1 ] ] ) ) ++j; upmax( ans, 2.0 + eu_dis( X[ stk[ i ] ], Y[ stk[ i ] ], X[ stk[ j ] ], Y[ stk[ j ] ] ) ); } } cout << fixed << setprecision( 8 ) << ans << endl; }
