首页 > 代码库 > BZOJ4520: [Cqoi2016]K远点对
BZOJ4520: [Cqoi2016]K远点对
题意:给定1e5个点,求第K远点对(K<=100)
题解:做法很多,可以旋转卡壳,也可以三分,还能KD_Tree。这里写的是KD_Tree。
用一个一开始装了2*K个0的优先队列记录答案,对于每一个点丢进去查,多的弹出来,再加进去。
巨TM有毒,调了2h,原因是对于每一个平面的划分点,我是在nth_element之前就选定了。但这样是不行的,排了之后它就跑掉了。。所以要么排了之后再选要么找划分点的时候直接根据l,r求出mid。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 #define N 100005 5 #define sqr(x) ((x)*(x)) 6 #define INF ((LL)1<<62) 7 8 inline LL read(){ 9 LL x=0,f=1; char a=getchar(); 10 while(a<‘0‘ || a>‘9‘) {if(a==‘-‘) f=-1; a=getchar();} 11 while(a>=‘0‘ && a<=‘9‘) x=x*10+a-‘0‘,a=getchar(); 12 return x*f; 13 } 14 15 int n,K; 16 priority_queue<LL>q; 17 18 struct point{ 19 LL x,y; 20 }p[N],v; 21 22 inline bool cmpx(const point& a,const point& b){return a.x<b.x;} 23 inline bool cmpy(const point& a,const point& b){return a.y<b.y;} 24 25 namespace KDT{ 26 int root,cnt; 27 28 struct kd{ 29 int l,r,son[2],kind; 30 LL xl,xr,yt,yb; 31 inline void init(){ 32 xl=yb=INF; xr=yt=0; 33 } 34 }a[2*N]; 35 36 inline LL dis(int x){ 37 point mid=p[(a[x].l+a[x].r)>>1]; 38 return sqr(mid.x-v.x)+sqr(mid.y-v.y); 39 } 40 41 inline LL get(int k){ 42 if(!k) return 0; 43 LL t1=max(sqr(a[k].xl-v.x),sqr(a[k].xr-v.x)); 44 LL t2=max(sqr(a[k].yb-v.y),sqr(a[k].yt-v.y)); 45 return t1+t2; 46 } 47 48 void build(int& k,int l,int r){ 49 if(l>r) return; 50 k=++cnt; 51 a[k].l=l; a[k].r=r; a[k].init(); 52 for(int i=l;i<=r;i++){ 53 a[k].xl=min(a[k].xl,p[i].x); 54 a[k].xr=max(a[k].xr,p[i].x); 55 a[k].yb=min(a[k].yb,p[i].y); 56 a[k].yt=max(a[k].yt,p[i].y); 57 } 58 int mid=(l+r)>>1,F; 59 if(l==r) return; 60 a[k].kind=F=a[k].xr-a[k].xl>a[k].yt-a[k].yb?0:1; 61 if(!F) nth_element(p+l,p+mid,p+r+1,cmpx); 62 else nth_element(p+l,p+mid,p+r+1,cmpy); 63 build(a[k].son[0],l,mid-1); build(a[k].son[1],mid+1,r); 64 } 65 66 void query(int k){ 67 LL d=dis(k),d1=get(a[k].son[0]),d2=get(a[k].son[1]); 68 if(-d<q.top()) q.pop(),q.push(-d); 69 if(d1>d2){ 70 if(-d1<q.top()) query(a[k].son[0]); 71 if(-d2<q.top()) query(a[k].son[1]); 72 }else{ 73 if(-d2<q.top()) query(a[k].son[1]); 74 if(-d1<q.top()) query(a[k].son[0]); 75 } 76 } 77 78 } 79 80 int main(){ 81 n=read(); K=read(); 82 for(int i=1;i<=2*K;i++) q.push(0); 83 for(int i=1;i<=n;i++) p[i].x=read(),p[i].y=read(); 84 KDT::build(KDT::root,1,n); 85 for(int i=1;i<=n;i++) v=p[i],KDT::query(KDT::root); 86 printf("%lld\n",-q.top()); 87 return 0; 88 }
BZOJ4520: [Cqoi2016]K远点对
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。