你知道欧几里得怎么转曼哈顿吗

Mini_PEKKA · 2026-03-04 20:54:44 · 题解

可以转化为对于距离 \le r 的点对连边，再对于每一个点判定其能否到达一个奇环。

对于一个点 i 以其为圆心画一个半径为 r 的圆，如果这个圆中其它点的个数 >5 则一定存在两个其它点距离 \le r，于是这两个其它点和 i 构成奇环，就不用管 i 了。如果个数 \le 5 就从 i 向这些点连边表示 i 可以往这些点走来到达一个奇环。

问题在于怎么快速找到离一个点第一到第六近的点。

由于欧几里得距离公式比较复杂，所以用曼哈顿距离对其进行估计，即每次找到与 i 曼哈顿距离最小的点并删掉，如果找到的点真的距离 i\le r 就算上，找到 6 个就停。

一个比较重要的剪枝是如果找到的点与 i 的曼哈顿距离 >\sqrt 2r 也停。因为可以证明任何距离 i\le r 的点与 i 的曼哈顿距离都 \le\sqrt 2r。

实现可以将点按 x 坐标升序排序然后正着和反着各扫描线一次，用线段树维护区间 x+y/x-y 的最小/大值。时间复杂度 \mathcal{O}(n\log n)。

时间复杂度可以感性理解：与 i 曼哈顿距离 \le\sqrt 2r 的范围是以 i 为圆心 r 为半径画出的圆的外接正方形，如果想把 i 找的次数卡得很大就必须要在圆与正方形之间的四个空中放很多点，但是这样的话这些点又很容易找到奇环，所以是均摊的。