关于这道题玄学做法的可能的hack

P1429 平面最近点对(加强版)

Player3476 @ 2024-02-18 15:59:34

玄学做法(随机旋转,取5个点)肯定是不能被完全hack的,只能降低通过的概率~ 这是一个六边星,每条边上最靠近中心的六个点(图中黄点)到中心的距离依次变远,红色线段长度为最短距离。在每个边上可以分布有很多个点。这样当一条边转到几乎与y轴垂直时,这种方法就不会正确。

如果把这个星的边数增多,变成100,1000边,效果会更好~(但是同时也要注意相邻两边上点的间距问题,可以通过“交叉放置”点的方式解决)


by CEFqwq @ 2024-02-18 20:25:46

@Player3476 但是跑更多遍还是可以做,而且这种做法真的很快。。。

另:我测试了一下,枚举 [i+1,i+3] 可以过,而且 8 个测试点只计算和 i+1 的距离都能过。


|