2716:[Violet 3]エンジェルドール/2648:SJY振り駒
7153 ワード
タイトルリンク
平面の動的な点をプラスして、与える点マンハッタンと距離の最も近い点を求めます
問題解:KDツリーテンプレート問題
私の収穫:23333
平面の動的な点をプラスして、与える点マンハッタンと距離の最も近い点を求めます
問題解:KDツリーテンプレート問題
私の収穫:23333
#include
#include
#include
#include
#include
using namespace std;
#define cmin(a,b) (a>b?a=b:a)
#define cmax(a,b) (a
const int N=1000010;
const int INF=0x3f3f3f3f;
int n,q,D,root,cnt,ans,nert;
int P[2];
int c[N][2],d[N][2],mi[N][2],mx[N][2];
struct abc{
int d[2];
int& operator[](int x){return d[x];}
}a[N];
bool operator return x[D]struct KDTree{
int Dis(int now){return abs(d[now][0]-P[0])+abs(d[now][1]-P[1]);}
int getdis(int now){return max(mi[now][0]-P[0],0)+max(P[0]-mx[now][0],0)+max(mi[now][1]-P[1],0)+max(P[1]-mx[now][1],0);}
void update(int x){
for(int i=0;i<2;i++){
if(c[x][0]) cmin(mi[x][i],mi[c[x][0]][i]),cmax(mx[x][i],mx[c[x][0]][i]);
if(c[x][1]) cmin(mi[x][i],mi[c[x][1]][i]),cmax(mx[x][i],mx[c[x][1]][i]);
}
}
int build(int l,int r,int x)
{
D=x;int m=l+r>>1;
nth_element(a+l,a+m,a+r+1);
for(int i=0;i<2;i++) d[m][i]=mi[m][i]=mx[m][i]=a[m][i];
if(l0]=build(l,m-1,x^1);
if(r>m) c[m][1]=build(m+1,r,x^1);
update(m);return m;
}
void insert(int &now,int x){
if(!now){now=++n;for(int i=0;i<2;i++) d[now][i]=mi[now][i]=mx[now][i]=P[i];return ;}
int tmp=P[x]>=d[now][x];
insert(c[now][tmp],x^1);
update(now);
}
void query(int x)
{
int tmp=Dis(x),dl[2];
for(int i=0;i<2;i++) dl[i]=c[x][i]?getdis(c[x][i]):INF;
cmin(ans,tmp);tmp=dl[0]>=dl[1];
if(dl[tmp]1;
if(dl[tmp]void work()
{
int opt;
for(int i=1;i<=q;i++)
{
scanf("%d%d%d",&opt,&P[0],&P[1]);
if(opt==1) T.insert(root,0);
else ans=INF,T.query(root),printf("%d
",ans);
}
}
void init()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++) scanf("%d%d",&a[i][0],&a[i][1]);
root=T.build(1,n,0);
}
int main()
{
init();
work();
return 0;
}