140 lines
3.8 KiB
C++
140 lines
3.8 KiB
C++
#include <cstdio>
|
|
#include <cstdlib>
|
|
#include <cstring>
|
|
#include <iostream>
|
|
#include <algorithm>
|
|
using namespace std;
|
|
#define N 100010
|
|
#define M 260010
|
|
typedef long long LL;
|
|
struct node{
|
|
LL x,y;
|
|
int id;
|
|
}w[150010];
|
|
LL ty[150010],ans[100010];
|
|
int ny;
|
|
struct Tree{
|
|
int l,r;
|
|
LL val;
|
|
}tree[1050010];
|
|
bool cmp1(const node &a,const node &b){
|
|
if(a.x!=b.x) return a.x<b.x;
|
|
if(a.y!=b.y) return a.y<b.y;
|
|
return a.id<b.id;
|
|
}
|
|
bool cmp2(const node &a,const node &b){
|
|
if(a.x!=b.x) return a.x<b.x;
|
|
if(a.y!=b.y) return a.y>b.y;
|
|
return a.id<b.id;
|
|
}
|
|
bool cmp3(const node &a,const node &b){
|
|
if(a.x!=b.x) return a.x>b.x;
|
|
if(a.y!=b.y) return a.y<b.y;
|
|
return a.id<b.id;
|
|
}
|
|
bool cmp4(const node &a,const node &b){
|
|
if(a.x!=b.x) return a.x>b.x;
|
|
if(a.y!=b.y) return a.y>b.y;
|
|
return a.id<b.id;
|
|
}
|
|
int findy(LL y){
|
|
int l=0,r=ny-1;
|
|
while(l<=r){
|
|
int mid=(l+r)>>1;
|
|
if(ty[mid]<y) l=mid+1;
|
|
else if(ty[mid]>y) r=mid-1;
|
|
else return mid+1;
|
|
}
|
|
}
|
|
void build(int L,int R,int x){
|
|
tree[x].l=L;
|
|
tree[x].r=R;
|
|
tree[x].val=1000000000000;
|
|
if(L==R) return ;
|
|
int mid=(L+R)>>1;
|
|
build(L,mid,x<<1);
|
|
build(mid+1,R,x<<1|1);
|
|
}
|
|
LL find(int L,int R,int x){
|
|
if(tree[x].l>=L&&tree[x].r<=R)
|
|
return tree[x].val;
|
|
int mid=(tree[x].l+tree[x].r)>>1;
|
|
if(R<=mid) return find(L,R,x<<1);
|
|
if(L>mid) return find(L,R,x<<1|1);
|
|
return min(find(L,mid,x<<1),find(mid+1,R,x<<1|1));
|
|
}
|
|
void update(int id,int x,LL val){
|
|
if(tree[x].l==tree[x].r){
|
|
tree[x].val=min(tree[x].val,val);
|
|
return ;
|
|
}
|
|
int mid=(tree[x].l+tree[x].r)>>1;
|
|
if(id<=mid) update(id,x<<1,val);
|
|
else update(id,x<<1|1,val);
|
|
tree[x].val=min(tree[x<<1].val,tree[x<<1|1].val);
|
|
}
|
|
int main(){
|
|
int n,q,cs=0;
|
|
while(scanf("%d",&n)&&n!=-1){
|
|
if(cs) printf("\n");
|
|
else cs=1;
|
|
for(int i=0;i<n;++i){
|
|
scanf("%lld%lld",&w[i].x,&w[i].y);
|
|
w[i].id=-1;
|
|
ty[i]=w[i].y;
|
|
}
|
|
scanf("%d",&q);
|
|
for(int i=0;i<q;++i){
|
|
ans[i]=1000000000000;
|
|
scanf("%lld%lld",&w[i+n].x,&w[i+n].y);
|
|
w[i+n].id=i;
|
|
ty[i+n]=w[i+n].y;
|
|
}
|
|
sort(ty,ty+n+q);
|
|
ny=0;
|
|
for(int i=1;i<n+q;++i)
|
|
if(ty[i]!=ty[ny]) ty[++ny]=ty[i];
|
|
ny++;
|
|
LL my=ty[ny-1],iy=ty[0];
|
|
build(1,ny,1);
|
|
sort(w,w+n+q,cmp1);
|
|
LL mx=w[n+q-1].x,ix=w[0].x;
|
|
for(int i=0;i<n+q;++i){
|
|
if(w[i].id!=-1){
|
|
int j=findy(w[i].y);
|
|
ans[w[i].id]=min(ans[w[i].id],find(1,j,1)-(my-w[i].y)-(mx-w[i].x));
|
|
}
|
|
else update(findy(w[i].y),1,(my-w[i].y)+(mx-w[i].x));
|
|
}
|
|
build(1,ny,1);
|
|
sort(w,w+n+q,cmp2);
|
|
for(int i=0;i<n+q;++i){
|
|
if(w[i].id!=-1){
|
|
int j=findy(w[i].y);
|
|
ans[w[i].id]=min(ans[w[i].id],find(j,ny,1)-(w[i].y-iy)-(mx-w[i].x));
|
|
}
|
|
else update(findy(w[i].y),1,(w[i].y-iy)+(mx-w[i].x));
|
|
}
|
|
build(1,ny,1);
|
|
sort(w,w+n+q,cmp3);
|
|
for(int i=0;i<n+q;++i){
|
|
if(w[i].id!=-1){
|
|
int j=findy(w[i].y);
|
|
ans[w[i].id]=min(ans[w[i].id],find(1,j,1)-(my-w[i].y)-(w[i].x-ix));
|
|
}
|
|
else update(findy(w[i].y),1,(my-w[i].y)+(w[i].x-ix));
|
|
}
|
|
build(1,ny,1);
|
|
sort(w,w+n+q,cmp4);
|
|
for(int i=0;i<n+q;++i){
|
|
if(w[i].id!=-1){
|
|
int j=findy(w[i].y);
|
|
ans[w[i].id]=min(ans[w[i].id],find(j,ny,1)-(w[i].y-iy)-(w[i].x-ix));
|
|
}
|
|
else update(findy(w[i].y),1,(w[i].y-iy)+(w[i].x-ix));
|
|
}
|
|
for(int i=0;i<q;++i) printf("%lld\n",ans[i]);
|
|
}
|
|
return 0;
|
|
}
|