首页 > 代码库 > 【bzoj4520】 Cqoi2016—K远点对
【bzoj4520】 Cqoi2016—K远点对
http://www.lydsy.com/JudgeOnline/problem.php?id=4520 (题目链接)
题意
求平面内第K远点对的距离。
Solution
左转题解:jump
细节
刚开始我还开了两个堆,想想其实是没必要的→_→
距离什么的开LL
代码
// bzoj4520#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<vector>#include<cmath>#include<queue>#define LL long long#define inf 1<<30#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=100010;int n,m,D,K,rt;priority_queue<LL,vector<LL>,greater<LL> > q;struct KDtree { int l,r,v[2],mn[2],mx[2]; friend bool operator < (const KDtree a,const KDtree b) { return a.v[D]<b.v[D]; }}tr[maxn],S;void update(int k) { for (int i=0;i<=1;i++) { if (tr[k].l) { tr[k].mn[i]=min(tr[k].mn[i],tr[tr[k].l].mn[i]); tr[k].mx[i]=max(tr[k].mx[i],tr[tr[k].l].mx[i]); } if (tr[k].r) { tr[k].mn[i]=min(tr[k].mn[i],tr[tr[k].r].mn[i]); tr[k].mx[i]=max(tr[k].mx[i],tr[tr[k].r].mx[i]); } }}int build(int l,int r,int p) { D=p; int mid=(l+r)>>1; nth_element(tr+l,tr+mid,tr+r+1); if (l<mid) tr[mid].l=build(l,mid-1,p^1); if (r>mid) tr[mid].r=build(mid+1,r,p^1); update(mid); return mid;}LL dis(LL x1,LL y1,LL x2,LL y2) { return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);}LL eva(int k) { LL lu=dis(S.v[0],S.v[1],tr[k].mn[0],tr[k].mn[1]); LL ru=dis(S.v[0],S.v[1],tr[k].mx[0],tr[k].mn[1]); LL ld=dis(S.v[0],S.v[1],tr[k].mn[0],tr[k].mx[1]); LL rd=dis(S.v[0],S.v[1],tr[k].mx[0],tr[k].mx[1]); return max(max(lu,ru),max(ld,rd));}void query(int k) { if (!k) return; LL d=dis(S.v[0],S.v[1],tr[k].v[0],tr[k].v[1]); if (q.top()<d) q.pop(),q.push(d); LL dl=eva(tr[k].l),dr=eva(tr[k].r); if (dl>dr) { if (q.top()<dl) query(tr[k].l); if (q.top()<dr) query(tr[k].r); } else { if (q.top()<dr) query(tr[k].r); if (q.top()<dl) query(tr[k].l); }} int main() { scanf("%d%d",&n,&K); for (int i=1;i<=n;i++) { scanf("%d%d",&tr[i].v[0],&tr[i].v[1]); tr[i].mn[0]=tr[i].mx[0]=tr[i].v[0]; tr[i].mn[1]=tr[i].mx[1]=tr[i].v[1]; } rt=build(1,n,0); for (int i=1;i<=2*K;i++) q.push(0); for (int i=1;i<=n;i++) S=tr[i],query(rt); printf("%lld",q.top()); return 0;}
【bzoj4520】 Cqoi2016—K远点对
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。