模板题 题意说的可能有点不清楚 一开始的点必须在给定的n个点里面
所以枚举点 然后ask最大和最小值
估价函数中 最大值的写法和最小值不同 全部取max
而最小值在估价时 如果在某个点管辖的空间里 就视为距离=0
估价函数如果写错 可能会导致wa or t
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<math.h>
#include<queue>
#include<string>
using namespace std;
#define L long long
const int INF = 999999999 ;
int n , root , cmp_d ;
struct node{
int d[2] , Max[2] , Min[2];
int l , r ;
}a[500050] ;
bool cmp(node a,node b){
return ((a.d[cmp_d] < b.d[cmp_d]) || (a.d[cmp_d] == b.d[cmp_d] && a.d[!cmp_d] < b.d[!cmp_d])) ;
}
void up(int p , int k ){
a[p].Max[0] = max(a[p].Max[0] , a[k].Max[0]);
a[p].Max[1] = max(a[p].Max[1] , a[k].Max[1]);
a[p].Min[0] = min(a[p].Min[0] , a[k].Min[0]);
a[p].Min[1] = min(a[p].Min[1] , a[k].Min[1]);
}
int build(int l, int r , int D ) {
int mid = (l+r) >> 1 ;
cmp_d = D;
nth_element(a+1+l,a+1+mid,a+1+r,cmp) ;
a[mid].Max[0] = a[mid].Min[0] = a[mid].d[0];
a[mid].Max[1] = a[mid].Min[1] = a[mid].d[1];
if(l != mid)
a[mid].l = build(l,mid-1,D^1);
else a[mid].l = 0 ;
if(r != mid)
a[mid].r = build(mid+1,r,D^1);
else a[mid].r = 0 ;
if(a[mid].l)up(mid,a[mid].l);
if(a[mid].r)up(mid,a[mid].r);
return mid ;
}
int ans1 , ans2 ;
int x, y ;
int getMaxdis(int p) {
int res = 0 ;
res += max(max(x - a[p].Max[0] , a[p].Max[0] - x) , max(x - a[p].Min[0] , a[p].Min[0] - x)) ;
res += max(max(y - a[p].Max[1] , a[p].Max[1] - y) , max(y - a[p].Min[1] , a[p].Min[1] - y)) ;
return res ;
}
void query_Max(int p) {
int d0 ;
int dl,dr ;
d0 = abs(x - a[p].d[0]) + abs(y - a[p].d[1]) ;
if(d0 != 0) {
ans2 = max(ans2 , d0) ;
}
if(a[p].l)
dl = getMaxdis(a[p].l) ;
else dl = -INF ;
if(a[p].r)
dr = getMaxdis(a[p].r) ;
else dr = -INF ;
if(dl > dr) {
if(dl > ans2)query_Max(a[p].l) ;
if(dr > ans2)query_Max(a[p].r) ;
}
else {
if(dr > ans2)query_Max(a[p].r) ;
if(dl > ans2)query_Max(a[p].l) ;
}
}
int getMindis(int p) {
int res = 0 ;
if(x > a[p].Max[0]) res += x - a[p].Max[0] ;
if(x < a[p].Min[0]) res += a[p].Min[0] - x ;
if(y > a[p].Max[1]) res += y - a[p].Max[1] ;
if(y < a[p].Min[1]) res += a[p].Min[1] - y ;
return res ;
}
void query_Min(int p) {
int d0 , dl , dr ;
d0 = abs(a[p].d[0] - x) + abs(a[p].d[1] - y) ;
if(d0 != 0) {
ans1 = min(d0 , ans1) ;
}
if(a[p].l)
dl = getMindis(a[p].l) ;
else dl = INF ;
if(a[p].r)
dr = getMindis(a[p].r) ;
else dr = INF ;
if(dl < dr) {
if(dl < ans1)query_Min(a[p].l) ;
if(dr < ans1)query_Min(a[p].r) ;
}
else {
if(dr < ans1)query_Min(a[p].r) ;
if(dl < ans1)query_Min(a[p].l) ;
}
}
int main(){
int n ;
scanf("%d",&n);
for(int i = 1; i <= n ; i ++ ){
scanf("%d%d",&a[i].d[0],&a[i].d[1]) ;
}
root = build(1,n,0) ;
int ans = INF ;
for(int i = 1; i <= n ; i ++ ){
ans1 = INF , ans2 = -INF ;
x = a[i].d[0] , y = a[i].d[1] ;
query_Max(root) ;
query_Min(root) ;
ans = min(ans , ans2 - ans1) ;
}
printf("%d\n",ans) ;
}