这是一份专为**信息学奥林匹克竞赛（信奥 / CP）**设计的解析几何与计算几何基础讲义。

在信奥中，解析几何往往与计算几何（Computational Geometry）紧密结合。为了避免斜率不存在（垂直于 $x$ 轴）等繁琐的分类讨论以及浮点数精度误差，竞赛中通常会引入**向量（Vector）**作为辅助工具。

---

# 信奥中的解析几何与计算几何讲义

## 一、 基础表示与精度控制（Precision & Representation）

在实数运算中，浮点数（`double`）存在精度误差。因此，我们在比较浮点数大小时，不能直接使用 `==` 或 `<`，而是需要引入一个极小值 $\epsilon$（通常取 `1e-9` 或 `1e-12`）。

### 1.1 精度控制代码模板
```cpp
#include <cmath>

const double eps = 1e-9;

// 符号函数：返回 -1 (负数), 0 (零), 1 (正数)
int sgn(double x) {
    if (fabs(x) < eps) return 0;
    return x < 0 ? -1 : 1;
}

// 比较两个浮点数大小
int cmp(double x, double y) {
    return sgn(x - y);
}
```

### 1.2 点与向量的结构体定义
在解析几何中，点和向量在坐标表示上是相同的，但在几何意义上不同。我们可以用同一个结构体统一定义，并重载常用运算符。

```cpp
struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
    
    // 向量加减法
    Point operator + (const Point& b) const { return Point(x + b.x, y + b.y); }
    Point operator - (const Point& b) const { return Point(x - b.x, y - b.y); }
    // 向量数乘
    Point operator * (double p) const { return Point(x * p, y * p); }
    Point operator / (double p) const { return Point(x / p, y / p); }
    
    // 比较运算符（用于排序，如极角排序或水平序）
    bool operator < (const Point& b) const {
        return cmp(x, b.x) == 0 ? cmp(y, b.y) < 0 : cmp(x, b.x) < 0;
    }
    bool operator == (const Point& b) const {
        return cmp(x - b.x, 0) == 0 && cmp(y - b.y, 0) == 0;
    }
};

typedef Point Vector; // 向量与点结构相同
```

---

## 二、 向量的核心运算（Vector Operations）

解析几何公式（如两点距离、夹角等）在程序中常常通过向量积来简化计算。

### 2.1 点积（Dot Product）
两个向量 $\vec{A} = (x\_1, y\_1)$ 和 $\vec{B} = (x\_2, y\_2)$ 的点积定义为：
$$\vec{A} \cdot \vec{B} = x\_1 x\_2 + y\_1 y\_2 = |\vec{A}| |\vec{B}| \cos\theta$$

**信奥中的应用**：
1. **求向量长度（模长）**：$|\vec{A}| = \sqrt{\vec{A} \cdot \vec{A}}$。
2. **夹角判断**：
   * $\vec{A} \cdot \vec{B} > 0 \iff$ 夹角为锐角（$< 90^\circ$）
   * $\vec{A} \cdot \vec{B} = 0 \iff$ 二者垂直（$= 90^\circ$）
   * $\vec{A} \cdot \vec{B} < 0 \iff$ 夹角为钝角（$> 90^\circ$）
3. **投影长度**：$\vec{A}$ 在 $\vec{B}$ 方向上的投影长度为 $\frac{\vec{A} \cdot \vec{B}}{|\vec{B}|}$。

```cpp
double dot(Vector A, Vector B) { return A.x * B.x + A.y * B.y; }
double length(Vector A) { return sqrt(dot(A, A)); }
```

### 2.2 叉积（Cross Product）
两个二维向量 $\vec{A} = (x\_1, y\_1)$ 和 $\vec{B} = (x\_2, y\_2)$ 的叉积定义为：
$$\vec{A} \times \vec{B} = x\_1 y\_2 - x\_2 y\_1 = |\vec{A}| |\vec{B}| \sin\theta$$
*(这里的 $\theta$ 是由 $\vec{A}$ 逆时针旋转到 $\vec{B}$ 的夹角)*

**信奥中的应用（极重要）**：
1. **方向判定（右手法则）**：
   * $\vec{A} \times \vec{B} > 0 \iff \vec{B}$ 在 $\vec{A}$ 的逆时针方向（左侧）。
   * $\vec{A} \times \vec{B} < 0 \iff \vec{B}$ 在 $\vec{A}$ 的顺时针方向（右侧）。
   * $\vec{A} \times \vec{B} = 0 \iff \vec{A}$ 与 $\vec{B}$ 共线（同向或反向）。
2. **面积计算**：由 $\vec{A}$ 和 $\vec{B}$ 围成的平行四边形有向面积为 $\vec{A} \times \vec{B}$；三角形面积为 $\frac{1}{2} | \vec{A} \times \vec{B} |$。

```cpp
double cross(Vector A, Vector B) { return A.x * B.y - A.y * B.x; }
// 两个向量围成的有向三角形面积的2倍（以A为起点，B, C为终点）
double area2(Point A, Point B, Point C) { return cross(B - A, C - A); }
```

---

## 三、 直线与线段（Lines and Line Segments）

### 3.1 直线的表示
在解析几何中，直线可以用一般式 $Ax + By + C = 0$ 表示。但在编程中，**参数式**更加通用且不易出错：
$$P(t) = P\_0 + t \cdot \vec{v}$$
其中 $P\_0$ 是直线上的一点，$\vec{v}$ 是方向向量，$t$ 为实数参数。

```cpp
struct Line {
    Point p;    // 直线上一点
    Vector v;   // 方向向量（不一定需要单位化）
    Line(Point p, Vector v) : p(p), v(v) {}
};
```

### 3.2 常用计算公式与实现

#### ① 点到直线的投影与最近点
若要找点 $Q$ 在直线 $L(P\_0, \vec{v})$ 上的投影点 $P'$：
$$P' = P\_0 + t \cdot \vec{v}, \quad \text{其中 } t = \frac{\overrightarrow{P\_0 Q} \cdot \vec{v}}{|\vec{v}|^2}$$

```cpp
Point get_line_projection(Point Q, Line L) {
    return L.p + L.v * (dot(Q - L.p, L.v) / dot(L.v, L.v));
}
```

#### ② 点到直线的距离
利用叉积求出有向面积，再除以底边长度即可得到高（即距离）：
$$d = \frac{|\overrightarrow{P\_0 Q} \times \vec{v}|}{|\vec{v}|}$$

```cpp
double distance_to_line(Point Q, Line L) {
    return fabs(cross(Q - L.p, L.v)) / length(L.v);
}
```

#### ③ 点到线段的距离
线段 $AB$ 上离 $Q$ 最近的点不一定是投影点（如果投影点落在线段外面，最近的点就是端点 $A$ 或 $B$）。因此需要分类讨论投影点的位置：

```cpp
double distance_to_segment(Point Q, Point A, Point B) {
    if (A == B) return length(Q - A); // 线段退化为点
    Vector v1 = B - A, v2 = Q - A, v3 = Q - B;
    if (sgn(dot(v1, v2)) < 0) return length(v2); // 投影在A外侧
    if (sgn(dot(v1, v3)) > 0) return length(v3); // 投影在B外侧
    return fabs(cross(v1, v2)) / length(v1);     // 投影在线段内
}
```

#### ④ 两直线交点
设直线 $L\_1: P + t \vec{v}$，直线 $L\_2: Q + w \vec{u}$。
利用叉积的比例关系，交点可以通过以下公式计算：

```cpp
Point get_line_intersection(Line L1, Line L2) {
    Vector u = L1.p - L2.p;
    double t = cross(L2.v, u) / cross(L1.v, L2.v);
    return L1.p + L1.v * t;
}
```
*注：调用前需保证 `sgn(cross(L1.v, L2.v)) != 0`，即两直线不平行。*

#### ⑤ 两线段相交判定
判断线段 $AB$ 和 $CD$ 是否相交，常用**快速排斥实验**和**跨立实验**。
* **跨立实验**：$AB$ 跨立 $CD$（即 $A, B$ 在直线 $CD$ 的两侧），且 $CD$ 跨立 $AB$。

```cpp
bool is_segment_intersection(Point A, Point B, Point C, Point D) {
    // 跨立实验
    double c1 = cross(B - A, C - A), c2 = cross(B - A, D - A);
    double c3 = cross(D - C, A - C), c4 = cross(D - C, B - C);
    return sgn(c1) * sgn(c2) < 0 && sgn(c3) * sgn(c4) < 0;
    // 注：若允许端点接触，需将上述判断条件改为 <= 0 并结合共线及范围检查
}
```

---

## 四、 圆与多边形（Circles and Polygons）

### 4.1 圆的结构表示
```cpp
struct Circle {
    Point c;   // 圆心
    double r;  // 半径
    Circle(Point c = Point(), double r = 0) : c(c), r(r) {}
    // 获取圆上某极角对应的点
    Point point(double a) {
        return Point(c.x + cos(a) * r, c.y + sin(a) * r);
    }
};
```

### 4.2 直线与圆的交点
通过圆心到直线的投影点 $P'$，以及弦长的一半 $L = \sqrt{r^2 - d^2}$，沿着直线的方向向量移动即可求出交点。

```cpp
// 返回交点数量，交点保存在 sol 中
int get_line_circle_intersection(Line L, Circle C, std::vector<Point>& sol) {
    double d = distance_to_line(C.c, L);
    int s = cmp(d, C.r);
    if (s > 0) return 0; // 相离
    Point p0 = get_line_projection(C.c, L);
    if (s == 0) { // 相切
        sol.push_back(p0);
        return 1;
    }
    // 相交
    double len = sqrt(C.r * C.r - d * d);
    Vector unit_v = L.v / length(L.v); // 方向单位向量
    sol.push_back(p0 + unit_v * len);
    sol.push_back(p0 - unit_v * len);
    return 2;
}
```

### 4.3 多边形面积计算（鞋带定理 / 鞋带公式）
任意多边形（包括凹多边形）都可以通过将其划分为以原点 $(0,0)$ 为顶点的三角形，利用叉积的有向面积进行累加求得。
设顶点逆时针依次为 $P\_1, P\_2, \dots, P\_n$：
$$S = \frac{1}{2} \sum\_{i=1}^n (x\_i y\_{i+1} - x\_{i+1} y\_i) \quad (\text{其中 } P\_{n+1} = P\_1)$$

```cpp
double polygon_area(const std::vector<Point>& p) {
    double area = 0;
    int n = p.size();
    for (int i = 0; i < n; i++) {
        area += cross(p[i], p[(i + 1) % n]);
    }
    return fabs(area) / 2.0;
}
```

---

## 五、 极坐标系与旋转（Polar Coordinates and Rotation）

在解决一些需要“扫描”或“按角度排序”的几何问题时，极坐标系和向量旋转是非常强大的工具。

### 5.1 向量的旋转
一个向量 $\vec{v} = (x, y)$ 逆时针旋转角度 $\theta$ 后，得到的新向量 $\vec{v}' = (x', y')$：
$$\begin{aligned}
x' &= x \cos\theta - y \sin\theta \\
y' &= x \sin\theta + y \cos\theta
\end{aligned}$$

```cpp
// 逆时针旋转 rad 弧度
Vector rotate(Vector A, double rad) {
    return Vector(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad));
}
```

### 5.2 极角排序（Polar Angle Sort）
极角排序在信奥算法中应用极广（如**Graham扫描法求凸包**、**旋转卡壳**、**极角扫描线**等）。
有两种常见的实现方式：

#### ① 使用 `atan2` 函数（高精度但略慢）
C++ 的标准库函数 `atan2(y, x)` 会返回 $(x, y)$ 与 $x$ 轴正半轴的夹角，范围在 $(-\pi, \pi]$ 之间。

```cpp
bool compare_by_atan2(const Point& a, const Point& b) {
    double angle_a = atan2(a.y, a.x);
    double angle_b = atan2(b.y, b.x);
    if (cmp(angle_a, angle_b) != 0) return angle_a < angle_b;
    return length(a) < length(b);
}
```

#### ② 使用叉积（全整数避开浮点误差，推荐用于第一、四象限或上半平面）
若点全部在 $x$ 轴右侧，我们可以直接使用叉积来确定极角先后关系：

```cpp
bool compare_by_cross(const Point& a, const Point& b) {
    double c = cross(a, b);
    if (sgn(c) != 0) return c > 0; // a 在 b 的顺时针方向，说明 a 的极角较小
    return length(a) < length(b);
}
```

---

## 六、 信奥实战：如何避免误差与极限思维

在正式的程序设计竞赛（如 NOI 系列赛、ACM/ICPC）中，由于解析几何常常伴随着巨大的数理推导，这里提供几条极为实用的编程避坑指南：

1. **尽可能使用全整数（Integer Geometry）**：
   如果输入的坐标都是整数，且问题只需要判断共线、相交或求面积大小关系，**绝对不要使用浮点数**。
   * 点积和叉积的计算全部用 `long long` 存储。
   * 比较距离时，直接比较距离的平方（即 `dot(A, A)`），不要使用 `sqrt` 开方。
2. **规范化参数式表示法**：
   在处理直线时，尽可能避免显式计算斜率 $k = \frac{\Delta y}{\Delta x}$。用“点 + 方向向量”作为直线的统一表达，可以让程序免受“斜率无穷大”的特判困扰。
3. **重视特退化情况（Degeneracy）**：
   在写完几何算法后，务必手动检查以下边界情况：
   * 三点共线。
   * 线段退化为一个点（起点与终点重合）。
   * 两个圆的圆心重合。
   * 直线平行或重合。

这是一份专为信息学奥林匹克竞赛（信奥 / CP）设计的解析几何与计算几何基础讲义。

在信奥中，解析几何往往与计算几何（Computational Geometry）紧密结合。为了避免斜率不存在（垂直于 $x$ 轴）等繁琐的分类讨论以及浮点数精度误差，竞赛中通常会引入向量（Vector）作为辅助工具。

信奥中的解析几何与计算几何讲义

一、基础表示与精度控制（Precision & Representation）

在实数运算中，浮点数（double）存在精度误差。因此，我们在比较浮点数大小时，不能直接使用 == 或 <，而是需要引入一个极小值 $\epsilon$（通常取 1e-9 或 1e-12）。

1.1 精度控制代码模板

#include <cmath>

const double eps = 1e-9;

// 符号函数：返回 -1 (负数), 0 (零), 1 (正数)
int sgn(double x) {
    if (fabs(x) < eps) return 0;
    return x < 0 ? -1 : 1;
}

// 比较两个浮点数大小
int cmp(double x, double y) {
    return sgn(x - y);
}

1.2 点与向量的结构体定义

在解析几何中，点和向量在坐标表示上是相同的，但在几何意义上不同。我们可以用同一个结构体统一定义，并重载常用运算符。

struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}

    // 向量加减法
    Point operator + (const Point& b) const { return Point(x + b.x, y + b.y); }
    Point operator - (const Point& b) const { return Point(x - b.x, y - b.y); }
    // 向量数乘
    Point operator * (double p) const { return Point(x * p, y * p); }
    Point operator / (double p) const { return Point(x / p, y / p); }

    // 比较运算符（用于排序，如极角排序或水平序）
    bool operator < (const Point& b) const {
        return cmp(x, b.x) == 0 ? cmp(y, b.y) < 0 : cmp(x, b.x) < 0;
    }
    bool operator == (const Point& b) const {
        return cmp(x - b.x, 0) == 0 && cmp(y - b.y, 0) == 0;
    }
};

typedef Point Vector; // 向量与点结构相同

二、向量的核心运算（Vector Operations）

解析几何公式（如两点距离、夹角等）在程序中常常通过向量积来简化计算。

2.1 点积（Dot Product）

两个向量 $\vec{A} = (x_1, y_1)$ 和 $\vec{B} = (x_2, y_2)$ 的点积定义为： $$\vec{A} \cdot \vec{B} = x_1 x_2 + y_1 y_2 = |\vec{A}| |\vec{B}| \cos\theta$$

信奥中的应用： 1. 求向量长度（模长）：$|\vec{A}| = \sqrt{\vec{A} \cdot \vec{A}}$。 2. 夹角判断： * $\vec{A} \cdot \vec{B} > 0 \iff$ 夹角为锐角（$< 90^\circ$） * $\vec{A} \cdot \vec{B} = 0 \iff$ 二者垂直（$= 90^\circ$） * $\vec{A} \cdot \vec{B} < 0 \iff$ 夹角为钝角（$> 90^\circ$） 3. 投影长度：$\vec{A}$ 在 $\vec{B}$ 方向上的投影长度为 $\frac{\vec{A} \cdot \vec{B}}{|\vec{B}|}$。

double dot(Vector A, Vector B) { return A.x * B.x + A.y * B.y; }
double length(Vector A) { return sqrt(dot(A, A)); }

2.2 叉积（Cross Product）

两个二维向量 $\vec{A} = (x_1, y_1)$ 和 $\vec{B} = (x_2, y_2)$ 的叉积定义为： $$\vec{A} \times \vec{B} = x_1 y_2 - x_2 y_1 = |\vec{A}| |\vec{B}| \sin\theta$$ (这里的 $\theta$ 是由 $\vec{A}$ 逆时针旋转到 $\vec{B}$ 的夹角)

信奥中的应用（极重要）： 1. 方向判定（右手法则）： * $\vec{A} \times \vec{B} > 0 \iff \vec{B}$ 在 $\vec{A}$ 的逆时针方向（左侧）。 * $\vec{A} \times \vec{B} < 0 \iff \vec{B}$ 在 $\vec{A}$ 的顺时针方向（右侧）。 * $\vec{A} \times \vec{B} = 0 \iff \vec{A}$ 与 $\vec{B}$ 共线（同向或反向）。 2. 面积计算：由 $\vec{A}$ 和 $\vec{B}$ 围成的平行四边形有向面积为 $\vec{A} \times \vec{B}$；三角形面积为 $\frac{1}{2} | \vec{A} \times \vec{B} |$。

double cross(Vector A, Vector B) { return A.x * B.y - A.y * B.x; }
// 两个向量围成的有向三角形面积的2倍（以A为起点，B, C为终点）
double area2(Point A, Point B, Point C) { return cross(B - A, C - A); }

三、直线与线段（Lines and Line Segments）

3.1 直线的表示

在解析几何中，直线可以用一般式 $Ax + By + C = 0$ 表示。但在编程中，参数式更加通用且不易出错： $$P(t) = P_0 + t \cdot \vec{v}$$ 其中 $P_0$ 是直线上的一点，$\vec{v}$ 是方向向量，$t$ 为实数参数。

struct Line {
    Point p;    // 直线上一点
    Vector v;   // 方向向量（不一定需要单位化）
    Line(Point p, Vector v) : p(p), v(v) {}
};

3.2 常用计算公式与实现

① 点到直线的投影与最近点

若要找点 $Q$ 在直线 $L(P_0, \vec{v})$ 上的投影点 $P'$： $$P' = P_0 + t \cdot \vec{v}, \quad \text{其中 } t = \frac{\overrightarrow{P_0 Q} \cdot \vec{v}}{|\vec{v}|^2}$$

Point get_line_projection(Point Q, Line L) {
    return L.p + L.v * (dot(Q - L.p, L.v) / dot(L.v, L.v));
}

② 点到直线的距离

利用叉积求出有向面积，再除以底边长度即可得到高（即距离）： $$d = \frac{|\overrightarrow{P_0 Q} \times \vec{v}|}{|\vec{v}|}$$

double distance_to_line(Point Q, Line L) {
    return fabs(cross(Q - L.p, L.v)) / length(L.v);
}

③ 点到线段的距离

线段 $AB$ 上离 $Q$ 最近的点不一定是投影点（如果投影点落在线段外面，最近的点就是端点 $A$ 或 $B$）。因此需要分类讨论投影点的位置：

double distance_to_segment(Point Q, Point A, Point B) {
    if (A == B) return length(Q - A); // 线段退化为点
    Vector v1 = B - A, v2 = Q - A, v3 = Q - B;
    if (sgn(dot(v1, v2)) < 0) return length(v2); // 投影在A外侧
    if (sgn(dot(v1, v3)) > 0) return length(v3); // 投影在B外侧
    return fabs(cross(v1, v2)) / length(v1);     // 投影在线段内
}

④ 两直线交点

设直线 $L_1: P + t \vec{v}$，直线 $L_2: Q + w \vec{u}$。利用叉积的比例关系，交点可以通过以下公式计算：

Point get_line_intersection(Line L1, Line L2) {
    Vector u = L1.p - L2.p;
    double t = cross(L2.v, u) / cross(L1.v, L2.v);
    return L1.p + L1.v * t;
}

注：调用前需保证 sgn(cross(L1.v, L2.v)) != 0，即两直线不平行。

⑤ 两线段相交判定

判断线段 $AB$ 和 $CD$ 是否相交，常用快速排斥实验和跨立实验。 * 跨立实验：$AB$ 跨立 $CD$（即 $A, B$ 在直线 $CD$ 的两侧），且 $CD$ 跨立 $AB$。

bool is_segment_intersection(Point A, Point B, Point C, Point D) {
    // 跨立实验
    double c1 = cross(B - A, C - A), c2 = cross(B - A, D - A);
    double c3 = cross(D - C, A - C), c4 = cross(D - C, B - C);
    return sgn(c1) * sgn(c2) < 0 && sgn(c3) * sgn(c4) < 0;
    // 注：若允许端点接触，需将上述判断条件改为 <= 0 并结合共线及范围检查
}

四、圆与多边形（Circles and Polygons）

4.1 圆的结构表示

struct Circle {
    Point c;   // 圆心
    double r;  // 半径
    Circle(Point c = Point(), double r = 0) : c(c), r(r) {}
    // 获取圆上某极角对应的点
    Point point(double a) {
        return Point(c.x + cos(a) * r, c.y + sin(a) * r);
    }
};

4.2 直线与圆的交点

通过圆心到直线的投影点 $P'$，以及弦长的一半 $L = \sqrt{r^2 - d^2}$，沿着直线的方向向量移动即可求出交点。

// 返回交点数量，交点保存在 sol 中
int get_line_circle_intersection(Line L, Circle C, std::vector<Point>& sol) {
    double d = distance_to_line(C.c, L);
    int s = cmp(d, C.r);
    if (s > 0) return 0; // 相离
    Point p0 = get_line_projection(C.c, L);
    if (s == 0) { // 相切
        sol.push_back(p0);
        return 1;
    }
    // 相交
    double len = sqrt(C.r * C.r - d * d);
    Vector unit_v = L.v / length(L.v); // 方向单位向量
    sol.push_back(p0 + unit_v * len);
    sol.push_back(p0 - unit_v * len);
    return 2;
}

4.3 多边形面积计算（鞋带定理 / 鞋带公式）

任意多边形（包括凹多边形）都可以通过将其划分为以原点 $(0,0)$ 为顶点的三角形，利用叉积的有向面积进行累加求得。设顶点逆时针依次为 $P_1, P_2, \dots, P_n$： $$S = \frac{1}{2} \sum_{i=1}^n (x_i y_{i+1} - x_{i+1} y_i) \quad (\text{其中 } P_{n+1} = P_1)$$

double polygon_area(const std::vector<Point>& p) {
    double area = 0;
    int n = p.size();
    for (int i = 0; i < n; i++) {
        area += cross(p[i], p[(i + 1) % n]);
    }
    return fabs(area) / 2.0;
}

五、极坐标系与旋转（Polar Coordinates and Rotation）

在解决一些需要“扫描”或“按角度排序”的几何问题时，极坐标系和向量旋转是非常强大的工具。

5.1 向量的旋转

一个向量 $\vec{v} = (x, y)$ 逆时针旋转角度 $\theta$ 后，得到的新向量 $\vec{v}' = (x', y')$： $$\begin{aligned} x' &= x \cos\theta - y \sin\theta \ y' &= x \sin\theta + y \cos\theta \end{aligned}$$

// 逆时针旋转 rad 弧度
Vector rotate(Vector A, double rad) {
    return Vector(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad));
}

5.2 极角排序（Polar Angle Sort）

极角排序在信奥算法中应用极广（如Graham扫描法求凸包、旋转卡壳、极角扫描线等）。有两种常见的实现方式：

① 使用 `atan2` 函数（高精度但略慢）

C++ 的标准库函数 atan2(y, x) 会返回 $(x, y)$ 与 $x$ 轴正半轴的夹角，范围在 $(-\pi, \pi]$ 之间。

bool compare_by_atan2(const Point& a, const Point& b) {
    double angle_a = atan2(a.y, a.x);
    double angle_b = atan2(b.y, b.x);
    if (cmp(angle_a, angle_b) != 0) return angle_a < angle_b;
    return length(a) < length(b);
}

② 使用叉积（全整数避开浮点误差，推荐用于第一、四象限或上半平面）

若点全部在 $x$ 轴右侧，我们可以直接使用叉积来确定极角先后关系：

bool compare_by_cross(const Point& a, const Point& b) {
    double c = cross(a, b);
    if (sgn(c) != 0) return c > 0; // a 在 b 的顺时针方向，说明 a 的极角较小
    return length(a) < length(b);
}

六、信奥实战：如何避免误差与极限思维