In the front

At first sight, I thought it was the Steiner tree Found out wrong
I went to the question solution and found that it was KD tree template question??? me may be really stupid

subject

BZOJ1941 transfer gate

General idea of the topic

Given N points on the plane, now we need to select a point from it, so that the distance from the farthest point to it and the distance from the nearest point to it is the smallest difference, and the output is the smallest difference.

I / O format

Input format:
The first line is an integer N, representing the number of points
Next N lines, each line is represented by a pair of coordinates of a point

Output format:
Output answer

solution

KD tree sub problem, first build the whole tree, and then ask the farthest point and the nearest point for each point.
For the complexity of KD tree, me has been searching on the Internet for a long time. The most rational formula is Q(n)=2+2Q(n/4) ⟹ Q=N − √ Q(n)=2+2Q(n/4) ⟹ Q=N, where q is the number of intervals divided by a line.
So the complexity of metaphysics is too high=

Here is the code with large constants

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

int N , ans , global_D , maxdis , mindis ;
template <typename T>
void smax( T&x , T y ){ if( x < y ) x = y ; }
template <typename T>
void smin( T&x , T y ){ if( x > y ) x = y ; }
template <typename T>
T abs_( T x ){ return x > 0 ? x : -x ; }

struct Node{
    int d[2] , maxn[2] , minn[2] ;
    Node *ch[2] ;
    void update(){
        maxn[0] = minn[0] = d[0] ;
        maxn[1] = minn[1] = d[1] ;
        if( ch[0] ){
            smax( maxn[0] , ch[0]->maxn[0] ) ;
            smax( maxn[1] , ch[0]->maxn[1] ) ;
            smin( minn[0] , ch[0]->minn[0] ) ;
            smin( minn[1] , ch[0]->minn[1] ) ;

        } if( ch[1] ){
            smax( maxn[0] , ch[1]->maxn[0] ) ;
            smax( maxn[1] , ch[1]->maxn[1] ) ;
            smin( minn[0] , ch[1]->minn[0] ) ;
            smin( minn[1] , ch[1]->minn[1] ) ;
        }
    }
} w[500005] , *root ;

bool cmp( const Node &A , const Node &B ){
    return A.d[ global_D ] < B.d[ global_D ] ||
        ( A.d[ global_D ] == B.d[ global_D ] && A.d[ global_D^1 ] < B.d[ global_D^1 ] ) ;
}

Node *build( int lf , int rg , int d ){
    int mid = ( lf + rg ) >> 1 ;
    global_D = d ;
    nth_element( w + lf , w + mid , w + rg + 1 , cmp ) ;
    Node *nd = &w[mid] ;
    if( lf < mid ) nd->ch[0] = build( lf , mid - 1 , d^1 ) ;
    if( rg > mid ) nd->ch[1] = build( mid + 1 , rg , d^1 ) ;
    nd->update() ;
    return nd ;
}

int dismax( Node *nd , int x , int y ){
    int rt = 0 ;
    rt += max( abs_( nd->maxn[0] - x ) , abs_( nd->minn[0] - x ) ) ;
    rt += max( abs_( nd->maxn[1] - y ) , abs_( nd->minn[1] - y ) ) ;
    return rt ;
}

int dismin( Node *nd , int x , int y ){
    int rt = 0 ;
    if( nd->minn[0] > x ) rt += nd->minn[0] - x ;
    if( nd->maxn[0] < x ) rt += x - nd->maxn[0] ;
    if( nd->minn[1] > y ) rt += nd->minn[1] - y ;
    if( nd->maxn[1] < y ) rt += y - nd->maxn[1] ;
    return rt ;
}

void Query_max( Node *nd , Node *aim ){
    if( nd != aim )
        smax( maxdis , abs_( nd->d[0] - aim->d[0] ) + abs_( nd->d[1] - aim->d[1] ) ) ;
    int disL = 0 , disR = 0 ;
    if( nd->ch[0] ) disL = dismax( nd->ch[0] , aim->d[0] , aim->d[1] ) ;
    if( nd->ch[1] ) disR = dismax( nd->ch[1] , aim->d[0] , aim->d[1] ) ;
    if( disL > disR ){
        if( maxdis < disL ) Query_max( nd->ch[0] , aim ) ;
        if( maxdis < disR ) Query_max( nd->ch[1] , aim ) ;
    } else {
        if( maxdis < disR ) Query_max( nd->ch[1] , aim ) ;
        if( maxdis < disL ) Query_max( nd->ch[0] , aim ) ;
    }
}

void Query_min( Node *nd , Node *aim ){
    if( nd != aim )
        smin( mindis , abs_( nd->d[0] - aim->d[0] ) + abs_( nd->d[1] - aim->d[1] ) ) ;
    int disL = 0x3f3f3f3f , disR = 0x3f3f3f3f ;
    if( nd->ch[0] ) disL = dismin( nd->ch[0] , aim->d[0] , aim->d[1] ) ;
    if( nd->ch[1] ) disR = dismin( nd->ch[1] , aim->d[0] , aim->d[1] ) ;
    if( disL < disR ){
        if( mindis > disL ) Query_min( nd->ch[0] , aim ) ;
        if( mindis > disR ) Query_min( nd->ch[1] , aim ) ;
    } else {
        if( mindis > disR ) Query_min( nd->ch[1] , aim ) ;
        if( mindis > disL ) Query_min( nd->ch[0] , aim ) ;
    }
}

int main(){
    scanf( "%d" , &N ) ;
    for( int i = 1 ; i <= N ; i ++ )
        scanf( "%d%d" , &w[i].d[0] , &w[i].d[1] ) ;
    root = build( 1 , N , 1 ) ;
    ans = 0x3f3f3f3f ;
    for( int i = 1 ; i <= N ; i ++ ){
        maxdis = 0 ; Query_max( root , &w[i] ) ;
        mindis = 0x3f3f3f3f ; Query_min( root , &w[i] ) ;
        smin( ans , maxdis - mindis ) ;
    }
    printf( "%d" , ans ) ;
}