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

发布于 2018-05-13  150 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

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

Description

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

Tag

KDT,堆

解决思路

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

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

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


HNCJ OIer