[BZOJ4520/Luogu4357][CQOI2016]K远点对(KDT,堆)

发布于 9 天前  21 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ4520/Luogu4357][CQOI2016]K远点对(KDT,堆)

Description

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

Tag

KDT,堆

解决思路

用小根堆维护当前得到的前K大的距离,用KDT优化暴力寻找距离的方式。
注意,由于在用KDT的时候点对是无序的,所以要存2K个值。

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ4520/Luogu4357][CQOI2016]K远点对(KDT,堆)


HNCJ OIer 一枚