【Bzoj4520】K远点对

来源和评测点

Bzoj4520

题目

【题目大意】
已知平面内N个点的坐标,求欧氏距离下的第K远点对。
【输入格式】
输入文件第一行为用空格隔开的两个整数N,K。
接下来N行,每行两个整数X,Y,表示一个点的坐标。
1<=N<=100000,1<=K<=100,K<=N*(N−1)/2,0<=X,Y<2^31。
【输出格式】
出文件第一行为一个整数,表示第K远点对的距离的平方(一定是个整数)。
【输入样例】
10 5
0 0
0 1
1 0
1 1
2 0
2 1
1 2
0 2
3 0
3 1
【输出样例】
9

刷题记录

20min

分析

kdtree,k固定
因为每个距离维护了两次,用2*k大小的小根堆维护,
相当于维护了前k个值,并且堆顶正是第k个

长姿势:
对于k确定的第k大,用一个堆维护会灰常方便

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
//Zory-2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
typedef unsigned long long ll;//严格来说这样才对
ll mymin(ll x,ll y) {return x<y?x:y;}
ll mymax(ll x,ll y) {return x>y?x:y;}
ll myabs(ll x) {return x>0?x:-x;}
ll mysqr(ll x) {return x*x;}
//*******************全局常量*******************
const int MAXN=110000;
const int INF=0x3f3f3f3f;
//*******************全局定义*******************
struct nod
{
ll d[2];//自己
ll mi[2],mx[2];//管理区间
int son[2];//左右区间
nod()
{
son[0]=son[1]=0;
}
}p[MAXN];
//*******************kdtree*******************
int D;
bool cmp(nod a,nod b)
{
return (a.d[D]<b.d[D]) or (a.d[D]==b.d[D] and a.d[1-D]<b.d[1-D]);
}
void update(int f,int x)
{
p[f].mi[0]=mymin(p[f].mi[0],p[x].mi[0]);p[f].mx[0]=mymax(p[f].mx[0],p[x].mx[0]);
p[f].mi[1]=mymin(p[f].mi[1],p[x].mi[1]);p[f].mx[1]=mymax(p[f].mx[1],p[x].mx[1]);
}
ll getdis(int t,ll x,ll y)//估价最好情况
{
return mymax(mysqr(p[t].mi[0]-x),mysqr(p[t].mx[0]-x))+
mymax(mysqr(p[t].mi[1]-y),mysqr(p[t].mx[1]-y));
}
//*******************实现*******************
int root;
int build(int l,int r,int d)
{
if(l>r) return 0;
int mid=(l+r)/2;
D=d;nth_element(p+l,p+mid,p+r+1,cmp);//尽量平衡
p[mid].mi[0]=p[mid].mx[0]=p[mid].d[0];
p[mid].mi[1]=p[mid].mx[1]=p[mid].d[1];
if(l<=mid-1) p[mid].son[0]=build(l,mid-1,1-d),update(mid,p[mid].son[0]);
if(mid+1<=r) p[mid].son[1]=build(mid+1,r,1-d),update(mid,p[mid].son[1]);
return mid;
}
int cnt;
void insert(ll x,ll y)
{
int t=++cnt;
p[t].d[0]=p[t].mi[0]=p[t].mx[0]=x;
p[t].d[1]=p[t].mi[1]=p[t].mx[1]=y;
if(root==0) root=t;
else
{
int f=root;
for(D=0;1;D=1-D)
{
update(f,t);
int tmp=cmp(p[f],p[t]);
if(p[f].son[tmp]==0)
{
p[f].son[tmp]=t;
break;
}
f=p[f].son[tmp];
}
}
}
priority_queue< ll,vector<ll>,greater<ll> > q;
void ask(int t,ll x,ll y)
{
ll dis=mysqr(p[t].d[0]-x)+mysqr(p[t].d[1]-y);
if(dis!=0 and dis>q.top()) q.pop(),q.push(dis);
int lc=p[t].son[0],rc=p[t].son[1];
ll f[2];
f[0]=(lc>0)?getdis(lc,x,y):0;
f[1]=(rc>0)?getdis(rc,x,y):0;
bool tmp=(f[1]<=f[0]);
if(f[tmp]>q.top()) ask(p[t].son[tmp],x,y);
if(f[1-tmp]>q.top()) ask(p[t].son[1-tmp],x,y);
}
//*******************主函数*******************
int main()
{
int n,k;scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%lld%lld",&p[i].d[0],&p[i].d[1]);
root=build(1,n,0);
while(q.size()<2*k) q.push(0);
for(int i=1;i<=n;i++) ask(root,p[i].d[0],p[i].d[1]);
printf("%lld",q.top());
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/673d.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%