# Yuki 96 圏外です。( Union Find, Bucket, Furthest Pair, Convex Hull )

No.96 圏外です。 - yukicoder

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;
}
```