algo2017_week4_closest_pair_of_2D_points

#include<bits/stdc++.h>
#define MAX 7000
using namespace std;
template<typename X> inline X sqr(const X& a) {return a * a;}

struct Point{
    float x , y;
} mp[MAX] , mpy[MAX];


bool cx( Point a , Point b ) { return a.x < b.x; }
bool cy( Point a , Point b ) { return a.y < b.y; }


float dis( Point a , Point b ){ return sqrt( sqr( a.x - b.x ) + sqr( a.y - b.y ) ); }


float solve( int L , int R ){
    if( L >= R ) return 1e7;
    int mid = ( L + R ) / 2 , t = 0;

    float d = min( solve( L , mid ) , solve( mid + 1 , R ) );

    for( int i = mid ; i >= L && mp[mid].x - mp[i].x < d; --i ) mpy[t++] = mp[i];
    for( int i = mid + 1 ; i <= R && mp[i].x - mp[mid].x < d ; ++i ) mpy[t++] = mp[i];

    sort( mpy , mpy + t , cy );

    for( int i = 0 ; i < t - 1 ; ++i )
        for( int j = 1 ; j < 3 && i + j < t ; ++j )
            d = min( d , dis( mpy[i] , mpy[i + j] ) );

    return d;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T , n;
    cin >> T;
    while( T-- ){
        cin >> n;
        for( int i = 0 ; i < n ; i++ ) cin >> mp[i].x >> mp[i].y;
        sort( mp , mp + n , cx );
        float ans = solve( 0 , n - 1 );
        cout << fixed << setprecision(3) << ans << endl;
    }
    return 0;
}