題目大意:給出平面上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; }