UVA 10245 - The Closest Pair Problem ( D&C )

UVa Online Judge
I have read a few good sites for reference.
phoenixzhao.github.io
http://apir8181.github.io/algorithm/2014/10/02/closest_pair.html
A very classic problem for divide and conquer.
There are 3 ways to solve this, with D&C ( O( n lg n ) ), BST ( O( n lg n ) ), or hashing ( O( n ) ). For the last one, it is finely written in the first blog link. Nonetheless, I have attempted the first approach.
It goes like this, let's sort all the points by the x-coordinate. Then, we will choose the median of x - say it is mx - and divide the problem into 2 subproblems, one for all the points in the left of mx and the other for all the points in the right of mx. Now suppose we have solved both the subproblems, and have minimal value for each. Let us now have d for the minimal of the return value of the subproblems. We will be concerned about those pairs that pass through the line mx, because we haven't checked any of those. If we simply apply brute force here, the complexity will be O( n ^ 2 ). However, we know what the minimal distances of both sides are, hence we can choose to check only those points that lies within distance d ( in terms of only x - coordinate ) from mx, and also only those pairs that are distanced less than d in y - coordinate ).
Here is the magic, it can be proven that for each point that satisfies the former, there are at most 11 points that satisfies the latter. This can be proved very easily. Let's have a square of 2 * d height and 2 * d width, having the square not tilted and the vertical line mx crossing through exactly the middle of the width of the square. Then divide the square into 12 equal rectangles. We have the sides of each rectangle - 2 * d / 3 in height and d / 2 in width. The maximal length of 2 points lying in the same little square will be less than d. That is, no points will lie in the same little rectangle ( otherwise the value d computed from the subproblems will be contradicted ), we have proved by pigeon hole principle that there are at most 11 points lying in the region.
As the big picture, we will divide problems by the x-coordinates, and re-sort by the y-coordinates when the recursion runs back.
Therefore, the time complexity will be T( n ) = 2 * T( n / 2 ) + O( n ).
By Master Theorem, we have T( n ) = O( n lg n ).
( devsathish.wordpress.com )

const double DINF = 1e4;

bool cmp_y( const pdd &a, const pdd &b ){
    return a.second < b.second;
}

double rec_solve( vpd &p, int lb, int rb ){
    if( lb + 1 == rb ) return DINF;
    int m = lb + rb >> 1;

    double mx = p[ m ].first; // IMPORTANT, 'coz things will get shuffled'

    double d = min( rec_solve( p, lb, m ), rec_solve( p, m, rb ) );
    inplace_merge( p.begin() + lb, p.begin() + m, p.begin() + rb, cmp_y );

    vpd t;
    for( int i = lb; i < rb; ++i ){
        if( fabs( p[ i ].first - mx ) >= d ) continue;
        for( int j = t.size() - 1; j >= 0; --j ){
            double dx = p[ i ].first - t[ j ].first;
            double dy = p[ i ].second - t[ j ].second;
            if( dy >= d ) break;
            d = min( d, sqrt( dx * dx + dy * dy ) );
        }
        t.push_back( p[ i ] );
    }

    return d;
}

bool solve(){
    int N; cin >> N;
    if( N == 0 ) return false;

    vpd point( N );
    for( int i = 0; i < N; ++i )
        cin >> point[ i ].first >> point[ i ].second;

    sort( point.begin(), point.end() );

    double ans = rec_solve( point, 0, N );

    if( ans < DINF )
        cout << fixed << setprecision( 4 ) << ans << "\n";
    else
        cout << "INFINITY\n";

    return true;
}