极角排序、斜率与距离度量 (Polar Angles & Distance Metrics)¶
在许多平面几何与组合优化问题中，点之间的方向关系（角度、斜率）与空间度量（曼哈顿距离、切比雪夫距离）扮演着决定性角色。
本章系统梳理极角排序的实现技巧、斜率有理数无损哈希、曼哈顿与切比雪夫距离的等价转化定理，以及在 LeetCode 经典高频题中的巧妙应用。
1. 极角排序 (Polar Angle Sort)¶
极角排序是指以某一点 \(O\) 为原点，将平面上的其余各点按照极角（与正向 X 轴的夹角）从小到大进行排序。
1.1 实现方式一：标准库 atan2 排序¶
C++ 标准库函数 std::atan2(double y, double x) 返回点 \((x, y)\) 的极角，取值范围为 \([-\pi, \pi]\)：
#include <vector>
#include <cmath>
#include <algorithm>
struct Point {
double x, y;
};
void sortByAtan2(Point origin, std::vector<Point>& pts) {
std::sort(pts.begin(), pts.end(), [&](const Point& a, const Point& b) {
double angle_a = std::atan2(a.y - origin.y, a.x - origin.x);
double angle_b = std::atan2(b.y - origin.y, b.x - origin.x);
return angle_a < angle_b;
});
}
- 优点：能够天然处理全象限（包括负半轴），代码极短；
- 缺点：涉及浮点数三角函数运算，存在纳秒级常数开销与潜在浮点误差。
1.2 实现方式二：象限 + 叉积精确整数排序¶
若坐标均为整数且追求 100% 精确与极致效率，可使用象限划分结合叉积：
// 获取点所属象限 (1, 2, 3, 4)
int getQuadrant(const Point& p) {
if (p.x > 0 && p.y >= 0) return 1;
if (p.x <= 0 && p.y > 0) return 2;
if (p.x < 0 && p.y <= 0) return 3;
return 4; // p.x >= 0 && p.y < 0
}
bool polarCompare(const Point& a, const Point& b) {
int qa = getQuadrant(a);
int qb = getQuadrant(b);
if (qa != qb) return qa < qb;
// 同象限内通过叉积判断: 叉积大于 0 说明 a 在 b 的顺时针方向 (极角更小)
return 1LL * a.x * b.y - 1LL * a.y * b.x > 0;
}
2. 斜率表示与有理数无损哈希¶
在求解共线点问题（如 LeetCode 149）时，直接用 double 计算斜率 \(k = \frac{\Delta y}{\Delta x}\) 会因精度问题导致哈希表无法精准匹配，同时无法自然处理垂直线段（\(\Delta x = 0\)）。
2.1 最大公约数约分化简¶
我们将斜率表示为一个规范化的二元组 \((\Delta x, \Delta y)\)：
- 计算 \(\Delta x = x_2 - x_1\) 和 \(\Delta y = y_2 - y_1\)；
- 计算最大公约数 \(g = \gcd(|\Delta x|, |\Delta y|)\)；
- 约分：\(\Delta x \leftarrow \frac{\Delta x}{g}, \quad \Delta y \leftarrow \frac{\Delta y}{g}\)；
- 符号规范化（唯一性保证）：
- 若 \(\Delta x < 0\)，两边同乘 \(-1\)（保证分母始终非负）；
- 若 \(\Delta x == 0\)，统一规范化为 \((0, 1)\)；
- 若 \(\Delta y == 0\)，统一规范化为 \((1, 0)\)。
#include <numeric>
#include <utility>
std::pair<int, int> getNormalizedSlope(int x1, int y1, int x2, int y2) {
int dx = x2 - x1;
int dy = y2 - y1;
if (dx == 0) return {0, 1};
if (dy == 0) return {1, 0};
int g = std::gcd(dx, dy);
dx /= g;
dy /= g;
if (dx < 0) {
dx = -dx;
dy = -dy;
}
return {dx, dy};
}
3. 曼哈顿距离与切比雪夫距离转换¶
3.1 距离定义¶
对于平面上两点 \(P_1(x_1, y_1)\) 与 \(P_2(x_2, y_2)\)：
- 曼哈顿距离（\(L_1\) 范数）：\(d_1(P_1, P_2) = |x_1 - x_2| + |y_1 - y_2|\)
- 切比雪夫距离（\(L_\infty\) 范数）：\(d_\infty(P_1, P_2) = \max(|x_1 - x_2|, |y_1 - y_2|)\)
3.2 坐标旋转等价变换定理¶
曼哈顿转切比雪夫
将原坐标 \((x, y)\) 旋转 \(45^\circ\) 并放大 \(\sqrt{2}\) 倍，新坐标为：
则原坐标系下的曼哈顿距离等于新坐标系下的切比雪夫距离：
切比雪夫转曼哈顿
将原坐标 \((x, y)\) 转换为：
则原坐标系下的切比雪夫距离等于新坐标系下的曼哈顿距离。
核心应用：¶
曼哈顿距离的两个维度相互耦合（绝对值相加），难以独立维护；通过转换为切比雪夫距离，问题变为 \(\max(|x_1' - x_2'|, |y_1' - y_2'|)\)，\(X\) 轴与 \(Y\) 轴完全解耦，只需分别求出一维坐标的最值差即可！
4. LeetCode 经典真题精选与深度精析¶
-
LeetCode 149 - 直线上最多的点数 (Max Points on a Line)
困难提示
固定单点 + 斜率有理数约分哈希统计。
- 枚举每个点 \(i\) 作为直线的基准点；
- 遍历其余所有点 \(j > i\)，利用 \(\gcd\) 约分将斜率规范化为二元组 \((dx, dy)\)；
- 哈希表统计每种斜率出现的频次，取全局最大值 \(+ 1\)。
- 时间复杂度 \(\mathcal{O}(N^2)\)，空间复杂度 \(\mathcal{O}(N)\)。
-
LeetCode 1610 - 可见点的最大数目 (Maximum Number of Visible Points)
困难提示
atan2极角转换 + 数组倍长环形滑动窗口。- 与观察者重合的点天然可见，单独计数。
- 对其余所有点计算相对极角 \(\theta = \text{atan2}(\Delta y, \Delta x)\)，排序；
- 处理环形跨越边界技巧：将全数组复制一份追加到末尾，每个追加角加上 \(2\pi\)（\(360^\circ\)）；
- 双指针滑动窗口：维护窗口使得 \(angles[r] - angles[l] \le \text{angle}\)，求最大窗口长度并加上重合点数。时间复杂度 \(\mathcal{O}(N \log N)\)。
-
LeetCode 963 - 最小面积矩形 II (Minimum Area Rectangle II)
中等提示
矩形对角线中点与长度哈希。
- 矩形的两条对角线中点相同且长度相等。
- 枚举所有点对 \((P_i, P_j)\)，计算对角线长度平方 \(len = \text{dist}^2(P_i, P_j)\) 与中点坐标 \((x_1 + x_2, y_1 + y_2)\)；
- 用哈希表以
(中点坐标, 长度)为键，存储所有满足该条件的对角线点对； - 同一键下的任意两条对角线必然构成矩形，计算面积取最小值。时间复杂度 \(\mathcal{O}(N^2)\)。
-
LeetCode 1266 - 访问所有点的最小时间 (Minimum Time Visiting All Points)
简单提示
切比雪夫距离直接应用。
- 每次移动可以水平、垂直或对角线移动一格。从 \((x_1, y_1)\) 移动到 \((x_2, y_2)\) 的最少步数恰好就是两点间的切比雪夫距离 \(\max(|x_1 - x_2|, |y_1 - y_2|)\)。
- 顺序遍历累加相邻两点的切比雪夫距离即可。时间复杂度 \(\mathcal{O}(N)\)，空间复杂度 \(\mathcal{O}(1)\)。