BZOJ 1941 SDOI 2010 Hide and Seek K-D樹

BZOJ 1941 SDOI 2010 Hide and Seek K-D樹

題目大意：給出平面上n個點，一個點離所有點的最長距離和最短距離的差最小，求這個最小的差。

思路：50W的數據為何O(nsqrt(n))的暴力能過？？？

CODE：

#include 
#include 
#include 
#include 
#define MAX 500010
#define INF 0x3f3f3f3f
using namespace std;
#define min(a,b) ((a) < (b) ? (a):(b))
#define max(a,b) ((a) > (b) ? (a):(b))
 
int dim;
 
struct Point{
    int x,y;
     
    Point(int _,int __):x(_),y(__) {}
    Point() {}
    bool operator <(const Point &a)const {
        return dim ? x < a.x:y < a.y;
    }
    void Read() {
        scanf("%d%d",&x,&y);
    }
}point[MAX];
 
inline int Calc(const Point &p1,const Point &p2)
{
    return abs(p1.x - p2.x) + abs(p1.y - p2.y);
}
 
struct KDTree{
    KDTree *son[2];
    Point root;
    int x0,y0,x1,y1;
     
    KDTree(KDTree *_,KDTree *__,Point ___) {
        son[0] = _,son[1] = __;
        root = ___;
        x0 = x1 = ___.x;
        y0 = y1 = ___.y;
    }
    KDTree() {}
    void Maintain(KDTree *a) {
        x0 = min(x0,a->x0);
        x1 = max(x1,a->x1);
        y0 = min(y0,a->y0);
        y1 = max(y1,a->y1);
    }
    int DisMin(const Point &p) {
        int re = 0;
        if(p.x < x0) re += x0 - p.x;
        if(p.x > x1) re += p.x - x1;
        if(p.y < y0) re += y0 - p.y;
        if(p.y > y1) re += p.y - y1;
        return re;
    }
    int DisMax(const Point &p) {
        int re = 0;
        re += max(abs(p.x - x0),abs(p.x - x1));
        re += max(abs(p.y - y0),abs(p.y - y1));
        return re;
    }
}*root,none,*nil = &none;
 
int cnt;
 
KDTree *BuildTree(int l,int r,int d)
{
    if(l > r)    return nil;
    dim = d;
    int mid = (l + r) >> 1;
    nth_element(point + l,point + mid,point + r + 1);
    KDTree *re = new KDTree(BuildTree(l,mid - 1,!d),BuildTree(mid + 1,r,!d),point[mid]);
    if(re->son[0] != nil)    re->Maintain(re->son[0]);
    if(re->son[1] != nil)    re->Maintain(re->son[1]);
    return re;
}
 
int _min,_max;
 
void AskMin(KDTree *a,const Point &p)
{
    int dis = Calc(a->root,p);
    if(dis) _min = min(_min,dis);
    int l = a->son[0] == nil ? INF:a->son[0]->DisMin(p);
    int r = a->son[1] == nil ? INF:a->son[1]->DisMin(p);
    if(l < r) {
        if(a->son[0] != nil) AskMin(a->son[0],p);
        if(a->son[1] != nil && r <= _min) AskMin(a->son[1],p);
    }   
    else {
        if(a->son[1] != nil) AskMin(a->son[1],p);
        if(a->son[0] != nil && l <= _min) AskMin(a->son[0],p); 
    }
}
 
void AskMax(KDTree *a,const Point &p)
{
    int dis = Calc(a->root,p);
    _max = max(_max,dis);
    int l = a->son[0] == nil ? -INF:a->son[0]->DisMax(p);
    int r = a->son[1] == nil ? -INF:a->son[1]->DisMax(p);
    if(l > r) {
        if(a->son[0] != nil) AskMax(a->son[0],p);
        if(a->son[1] != nil && r >= _max) AskMax(a->son[1],p);
    }
    else {
        if(a->son[1] != nil) AskMax(a->son[1],p);
        if(a->son[0] != nil && l >= _max) AskMax(a->son[0],p);
    }
}
 
int main()
{
    cin >> cnt;
    for(int i = 1; i <= cnt; ++i)
        point[i].Read();
    root = BuildTree(1,cnt,0);
    int ans = INF;
    for(int i = 1; i <= cnt; ++i) {
        _min = INF,_max = -INF;
        AskMin(root,point[i]);
        AskMax(root,point[i]);
        ans = min(ans,_max - _min);
    }
    cout << ans << endl;
    return 0;
}