OJ-Problems-Source/HDOJ/4189_autoAC.cpp

140 lines
3.8 KiB
C++
Raw Permalink Normal View History

#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;
}