JZPFAR
题意：
给定平面上
N
N
N个点，然后
M
M
M个询问：给定一个点，求第
K
K
K远点。
思路：
K
K
K远点对的弱化版本？
建好普通的K-D Tree每次询问维护一个大小为
K
K
K的小顶堆即可剪枝也非常基础
代码
#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std
;
typedef long long ll
;
typedef pair
<ll
,int> pr
;
inline int read() {int x
=0,f
=1;char c
=getchar();while(c
!='-'&&(c
<'0'||c
>'9'))c
=getchar();if(c
=='-')f
=-1,c
=getchar();while(c
>='0'&&c
<='9')x
=x
*10+c
-'0',c
=getchar();return f
*x
;}
const int maxn
= 1e5+10;
const int inf
= 0x3f3f3f3f;
const int mod
= 1e9+7;
const double eps
= 1e-7;
int n
, m
, tot
, Dim
, rt
;
int ls
[maxn
], rs
[maxn
];
int mi
[maxn
][2], mx
[maxn
][2], sz
[maxn
];
inline ll
square(int x
) { return ll(x
)*x
; }
struct P
{
int x
[2], id
;
friend bool operator < (const P
&a
, const P
&b
) {
return a
.x
[Dim
]<b
.x
[Dim
];
}
inline ll
dis(const P
&rhs
) const {
return square(x
[0]-rhs
.x
[0])+square(x
[1]-rhs
.x
[1]);
}
}p
[maxn
], tmp
[maxn
], q
;
priority_queue
<pr
,vector
<pr
>,greater
<pr
> > Q
;
inline void Max(int &x
, int y
) { if(x
<y
) x
=y
; }
inline void Min(int &x
, int y
) { if(x
>y
) x
=y
; }
void push_up(int now
) {
for(int i
=0; i
<2; ++i
) {
mi
[now
][i
]=mx
[now
][i
]=p
[now
].x
[i
];
if(ls
[now
]) Min(mi
[now
][i
],mi
[ls
[now
]][i
]), Max(mx
[now
][i
],mx
[ls
[now
]][i
]);
if(rs
[now
]) Min(mi
[now
][i
],mi
[rs
[now
]][i
]), Max(mx
[now
][i
],mx
[rs
[now
]][i
]);
}
sz
[now
]=sz
[ls
[now
]]+sz
[rs
[now
]]+1;
}
void build(int l
, int r
, int dim
, int &now
) {
if(l
>r
) { now
=0; return; }
now
=++tot
;
int m
=(l
+r
)/2;
Dim
=dim
; nth_element(tmp
+l
,tmp
+m
,tmp
+r
+1); p
[now
]=tmp
[m
];
build(l
,m
-1,dim
^1,ls
[now
]); build(m
+1,r
,dim
^1,rs
[now
]);
push_up(now
);
}
inline ll
cal(int now
) {
return max(square(mi
[now
][0]-q
.x
[0]),square(mx
[now
][0]-q
.x
[0]))+max(square(mi
[now
][1]-q
.x
[1]),square(mx
[now
][1]-q
.x
[1]));
}
void query(int now
) {
if(!now
) return;
ll d0
=q
.dis(p
[now
]);
if(pr(d0
,-p
[now
].id
)>Q
.top()) Q
.pop(), Q
.push(pr(d0
,-p
[now
].id
));
int l
=ls
[now
], r
=rs
[now
];
ll dl
=cal(l
), dr
=cal(r
);
if(dl
<dr
) swap(l
,r
), swap(dl
,dr
);
if(dl
>=Q
.top().first
) query(l
);
if(dr
>=Q
.top().first
) query(r
);
}
int main() {
n
=read();
for(int i
=1; i
<=n
; ++i
) {
scanf("%d%d", &tmp
[i
].x
[0], &tmp
[i
].x
[1]);
tmp
[i
].id
=i
;
}
build(1,n
,0,rt
);
m
=read();
while(m
--) {
scanf("%d%d", &q
.x
[0], &q
.x
[1]);
int k
=read();
while(Q
.size()) Q
.pop();
for(int i
=0; i
<k
; ++i
) Q
.push(pr(0,-inf
));
query(rt
);
printf("%d\n", -Q
.top().second
);
}
}
