PKU 2187 Beauty Contest
http://poj.org/problem?id=2187
n個の点が与えられる。
これらの点のうち、任意の2点間の距離の二乗の最大値を求めろというような問題。
空間木的なものを初めて実装しました。
ある空間まで探索した後に、その空間内には今まで得た最大値より大きくなりそうな点がなければ探索を打ち切っています。
最初angをvectorでやっていたら、TLEになりました。
微妙に実装が面倒くさい気がするのに正解者数が多いのが個人的には謎。
typedef struct _node{ int x,y; int len; _node* ch[4]; int num; }node; PI in[50000]; node *root; node ent[500000]; int sz; bool rectin(int x,int y,int len,const PI&po){ return x<=po.F && y<=po.S && po.F<x+len && po.S<y+len; } void insert(const PI&po,node*&pa,int rx,int ry,int rlen){ if(rlen<1)return; if(!pa)pa=ent+sz++; pa->x=rx; pa->y=ry; pa->len=rlen; if(pa->len==1)return; int x=pa->x,y=pa->y,len=pa->len; if(rectin(x,y,len/2,po)){ insert(po,pa->ch[0],x,y,len/2); }else if(rectin(x+len/2,y,len-len/2,po)){ insert(po,pa->ch[1],x+len/2,y,len-len/2); }else if(rectin(x,y+len/2,len-len/2,po)){ insert(po,pa->ch[2],x,y+len/2,len-len/2); }else insert(po,pa->ch[3],x+len/2,y+len/2,len-len/2); } int ans; PI ang[4]; void getang(int x,int y,int len){ ang[0]=mp(x,y); ang[1]=mp(x+len-1,y); ang[2]=mp(x,y+len-1); ang[3]=mp(x+len-1,y+len-1); } void maxlen(const PI&po,node*pa){ //cout<<po.F<<' '<<po.S<<endl; //cout<<pa->x<<' '<<pa->y<<' '<<pa->len<<endl; if(pa->len==1){ int tx=po.F-pa->x,ty=po.S-pa->y; ans=max(ans,tx*tx+ty*ty); return; } int tmax=0; getang(pa->x,pa->y,pa->len); rep(i,4){ int tx=po.F-ang[i].F,ty=po.S-ang[i].S; tmax=max(tmax,tx*tx+ty*ty); } if(tmax<=ans)return; rep(i,4) if(pa->ch[i])maxlen(po,pa->ch[i]); } main(){ int n; scanf("%d",&n); rep(i,n){ scanf("%d%d",&in[i].F,&in[i].S); insert(in[i],root,-10000,-10000,20001); } rep(i,n)maxlen(in[i],root); cout<<ans<<endl; }