很神奇！

P1429 平面最近点对（加强版）

SkyWave @ 2022-12-11 10:30:55

分治解此题感觉是和暴力差不多的思路，但是时间复杂度却降到了O(n \log^2 n)，那分治法到底比暴力省了哪部分时间呢？

by Cerisier @ 2022-12-11 10:47:11

@SkyWave 暴力是将一些不可能的点也给枚举了，例如下图中红色两点，在暴力中会查到，但是分治不会：

by SkyWave @ 2022-12-11 10:47:55

@Cerisier ~~为什么不会呢~~

by Cerisier @ 2022-12-11 10:48:15

分治只考虑距离分割线不超过 d 的点

by Cerisier @ 2022-12-11 10:48:27

@SkyWave

by SkyWave @ 2022-12-11 10:54:05

@Cerisier 感谢