记录编号	576590	评测结果	AAAAAAAAAA
题目名称	3696.耍猴游戏	最终得分	100
用户昵称	op_组撒头屯	是否通过	通过
代码语言	C++	运行时间	0.243 s
提交时间	2022-10-12 19:25:36	内存使用	7.05 MiB

#include <bits/stdc++.h>
using namespace std;
const int N=100000+5;
const int T=10000+5;
const int inf=0x3f3f3f3f;
int n,m;
int x[N],y[N];
vector<int>v[T];
int ans=inf,a,b;
int getid(int x,int y){
    return ((x-1)/1000)*100+(y-1)/1000;
}
bool check(int id){
    for (int i=0;i<v[id].size();i++){
        ans=min(ans,abs(a-x[v[id][i]])+abs(b-y[v[id][i]]));
    }
    return v[id].size()!=0;
}
bool calc(int d,int id){
    bool yes=0;
    int yy=id%100,xx=(id-yy)/100;
    for (int i=max(0,yy-d),p=xx-d,q=xx+d;i<=min(99,yy+d);i++){
        if (p>=0)yes|=check(p*100+i);
        if (q<=99)yes|=check(q*100+i);
    }
    for (int i=max(0,xx-d),p=yy-d,q=yy+d;i<=min(99,xx+d);i++){
        if (p>=0)yes|=check(p+i*100);
        if (q<=99)yes|=check(q+i*100);
    }
    return yes;
}
int main(){
	freopen ("monkeygame.in","r",stdin);
	freopen ("monkeygame.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++){
	    scanf("%d%d",&x[i],&y[i]);
	    int id=getid(x[i],y[i]);
	    v[id].push_back(i);
    }
    while(m--){
        int opt;scanf("%d",&opt);
        if (opt==1){
            n++;
            scanf("%d%d",&x[n],&y[n]);
            int id=getid(x[n],y[n]);
	        v[id].push_back(n);
        }
        else{
            scanf("%d%d",&a,&b);
            int id=getid(a,b);ans=inf;
            if (check(id)){
                calc(1,id);calc(2,id);
                printf("%d\n",ans);
                continue;
            }
            int d=1;
            while(!calc(d,id))d++;
            calc(d+1,id);calc(d+2,id);
            printf("%d\n",ans);
        }
    }
    return 0;
}