堆維護第k大，每個點KD-Tree上A*式查詢較遠點，跑得飛快，復雜度玄學。

#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> using namespace std; #define ll long long #define N 100010 char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() {int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f; } int n,m,c,root,cnt; struct point {int d[2];bool operator <(const point&a) const{return d[c]<a.d[c];} }a[N]; struct KDTree{int ch[2],a[2][2];point p; }tree[N]; priority_queue<ll,vector<ll>,greater<ll> > q; ll sqr(int x){return 1ll*x*x;} ll dis(point u,point v){return sqr(u.d[0]-v.d[0])+sqr(u.d[1]-v.d[1]);} ll dis(point u,int a[2][2]){return sqr(max(u.d[0]-a[0][0],a[0][1]-u.d[0]))+sqr(max(u.d[1]-a[1][0],a[1][1]-u.d[1]));} void build(int &k,int l,int r,int op) {if (l>r) return;k=++cnt,c=op;int mid=l+r>>1;nth_element(a+l,a+mid,a+r+1);tree[k].p=a[mid];tree[k].a[0][0]=tree[k].a[0][1]=a[mid].d[0],tree[k].a[1][0]=tree[k].a[1][1]=a[mid].d[1];for (int i=l;i<=r;i++)tree[k].a[0][0]=min(tree[k].a[0][0],a[i].d[0]),tree[k].a[0][1]=max(tree[k].a[0][1],a[i].d[0]),tree[k].a[1][0]=min(tree[k].a[1][0],a[i].d[1]),tree[k].a[1][1]=max(tree[k].a[1][1],a[i].d[1]);build(tree[k].ch[0],l,mid-1,op^1);build(tree[k].ch[1],mid+1,r,op^1); } void query(int k,point p) {if (dis(tree[k].p,p)>=q.top()) q.push(dis(tree[k].p,p)),q.pop();int l=tree[k].ch[0],r=tree[k].ch[1];ll u=dis(p,tree[l].a),v=dis(p,tree[r].a);if (u<v) swap(l,r),swap(u,v);if (l&&u>=q.top()) query(l,p);if (r&&v>=q.top()) query(r,p); } int main() { #ifndef ONLINE_JUDGEfreopen("bzoj4520.in","r",stdin);freopen("bzoj4520.out","w",stdout);const char LL[]="%I64d\n"; #elseconst char LL[]="%lld\n"; #endifn=read(),m=read()<<1;for (int i=1;i<=n;i++) a[i].d[0]=read(),a[i].d[1]=read();build(root,1,n,0);while (m--) q.push(0);for (int i=1;i<=n;i++) query(root,a[i]);cout<<q.top();return 0; }

?

轉載于:https://www.cnblogs.com/Gloid/p/10161753.html

總結

以上是生活随笔為你收集整理的BZOJ4520 CQOI2016K远点对（KD-Tree+堆）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。