BZOJ 4520 [Cqoi2016]K 远点对

发布于 2017-07-11  164 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4520

题意:已知平面内 N 个点的坐标,求欧氏距离下的第 K 远点对。


直接 K-Dtree 暴力即可了... 一个小根堆维护所有 1-K 远点对,初始都是 0,每次枚举每个点去找比堆顶远的距离,更新堆顶,保证时刻堆都是 k 个元素。

最后输出堆顶即可。需要注意的是点对是无序的,那么需要维护 2*k 个

 


一个非常弱的准退役OIER