一个问题
查看原帖
一个问题
239241
Singercoder楼主2021/6/25 12:28

二分一个最小阈值d使得距离<=d的点对有>=k个,然后如果直接找出所有这些点对并将距离排序,点对数量将会>=k,但不知道有没有可能卡到足够大(直观来想貌似不太能的样子),或者证伪

比如,一个显然的想法是所有点坐标为(i×d,j×d)(i \times d,j \times d),这样点对数量达到2n,我想知道有没有可能更大

当然关于此,一个简单保险的处理方式是我们只去找<=d-1的点对,然后剩下不到k的部分用d补齐

2021/6/25 12:28
加载中...