//Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and 
// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the 
// same ids are connected.
// prefix 的格式要求是 acm-[一级标题编号].[二级标题编号][该代码片段的英文简称]
// description 的格式要求是 "插入 [该代码片段的中文名]"

{
    "极角排序": {
        "prefix": "acm-8.2sort",
        "body": [
            "#include <bits/stdc++.h>",
            "using namespace std;",
            "struct Point {",
            "\tlong long x, y;",
            "\t",
            "\t// 1. 象限划分 / 半平面划分",
            "\t// 规定极角从 x 轴正半轴开始，逆时针方向为正。",
            "\t// 我们将平面分为上下两个半区：",
            "\t// 上半区 (包含正 x 轴)：y > 0，或者 y == 0 且 x > 0 (返回 0)",
            "\t// 下半区 (包含负 x 轴)：y < 0，或者 y == 0 且 x < 0 (返回 1)",
            "\t// 原点 (0,0) 通常特殊处理或不参与极角排序，这里默认归为上半区",
            "\tint half() const {",
            "\t\tif (y > 0 || (y == 0 && x > 0)) return 0;",
            "\t\treturn 1;",
            "\t}",
            "};",
            "",
            "// 几何意义：以 OA 和 OB 为邻边的平行四边形的有向面积",
            "// 如果结果 > 0，说明从 OA 到 OB 是逆时针方向 (A 的极角小于 B 的极角)",
            "// 如果结果 < 0，说明是顺时针方向",
            "// 如果结果 == 0，说明 A, O, B 三点共线",
            "long long cross(Point a, Point b) {",
            "\treturn a.x * b.y - a.y * b.x;",
            "}",
            "",
            "// 3. 距离平方 (用于共线时的副关键字排序)",
            "long long dist2(Point a) {",
            "\treturn a.x * a.x + a.y * a.y;",
            "}",
            "",
            "// 4. 终极极角排序比较函数 (逆时针排列)",
            "bool polar_cmp(Point a, Point b) {",
            "\t// 步骤一：如果两个点在不同的半区，上半区的点一定排在前面",
            "\tif (a.half() != b.half()) {",
            "\t\treturn a.half() < b.half();",
            "\t}",
            "\t",
            "\tlong long cp = cross(a, b);",
            "\tif (cp != 0) {",
            "\t\t// cp > 0 表示 a 在 b 的顺时针方向（即 a 的角度更小）",
            "\t\treturn cp > 0; ",
            "\t}",
            "\t",
            "\t// 步骤三：如果极角完全相同 (共线)，通常把距离原点更近的点排在前面",
            "\treturn dist2(a) < dist2(b);",
            "}",
            "",
            "// ==========================================",
            "// 5. 实战用法示例",
            "// ==========================================",
            "void polar_sort_example() {",
            "\tvector<Point> pts = {",
            "{-2, -2}, {1, 1}, {-1, 1}, {2, 0}, {0, 2}, {1, -1}",
            "};",
            "\t",
            "\t// 假设以原点 (0,0) 为基准点进行极角排序",
            "\t// 如果基准点是其他的点 P，只需要把所有的点先减去 P (平移坐标系) 再排序即可",
            "\tsort(pts.begin(), pts.end(), polar_cmp);",
            "\t",
            "\t// 排序后的 pts 顺序将是严格的逆时针一圈",
            "}"
        ],
        "description": "插入 极角排序"
    }
}