用一根橡皮筋包住世界

if abs(cross) < 1e-9:
    cross = 0

math.atan2()

def cross(a, b, c):
    """
    计算向量 AB 与 AC 的二维叉积。

    > 0：逆时针方向（左转）
    < 0：顺时针方向（右转）
    = 0：共线
    """
    return (
        (b[0] - a[0]) * (c[1] - a[1])
        - (b[1] - a[1]) * (c[0] - a[0])
    )


print(cross((1, 1), (5, 1), (4, 4)))   # 12
print(cross((1, 1), (5, 1), (4, -1)))  # -8
print(cross((0, 0), (2, 2), (4, 4)))   # 0

from functools import cmp_to_key


def cross(a, b, c):
    return (
        (b[0] - a[0]) * (c[1] - a[1])
        - (b[1] - a[1]) * (c[0] - a[0])
    )


def graham_scan(points):
    """
    返回逆时针排列的凸包极端顶点。

    - 自动删除重复点
    - 不保留凸包直边上的中间共线点
    - 全部共线时返回两个端点
    - 使用整数坐标时方向判断为精确整数运算
    """

    pts = list(set(map(tuple, points)))

    if len(pts) <= 1:
        return pts

    # 选择最低点，纵坐标相同则选择最左点
    pivot = min(pts, key=lambda p: (p[1], p[0]))

    others = [p for p in pts if p != pivot]

    def distance2(p):
        return (
            (p[0] - pivot[0]) ** 2
            + (p[1] - pivot[1]) ** 2
        )

    def angle_compare(a, b):
        turn = cross(pivot, a, b)

        if turn > 0:
            return -1
        if turn < 0:
            return 1

        # 共线时，较近的点在前
        da, db = distance2(a), distance2(b)

        if da < db:
            return -1
        if da > db:
            return 1

        return 0

    others.sort(key=cmp_to_key(angle_compare))

    stack = [pivot]

    for p in others:
        while (
            len(stack) >= 2
            and cross(stack[-2], stack[-1], p) <= 0
        ):
            stack.pop()

        stack.append(p)

    return stack


points = [
    (10, 15),
    (26, 78),
    (38, 20),
    (53, 90),
    (86, 76),
    (94, 24),
    (66, 8),
    (45, 49),
    (73, 48),
    (22, 43),
]

hull = graham_scan(points)

print("凸包顶点数量:", len(hull))
print("凸包顶点:", hull)

for p in others:
    while ...:
        stack.pop()

tests = [
    # 重复点
    [(0, 0), (0, 0), (2, 0), (1, 1), (2, 0)],

    # 全部共线
    [(0, 0), (1, 1), (2, 2), (3, 3)],

    # 只有一个点
    [(7, 4)],

    # 正方形加中心点
    [
        (0, 0), (4, 0),
        (4, 4), (0, 4),
        (2, 2)
    ]
]

for points in tests:
    print(graham_scan(points))

long long cross = dx1 * dy2 - dy1 * dx2;

#include <cstdint>

struct Point {
    long long x, y;
};

__int128 orient(
    const Point& a,
    const Point& b,
    const Point& c
) {
    __int128 abx = (__int128)b.x - a.x;
    __int128 aby = (__int128)b.y - a.y;

    __int128 acx = (__int128)c.x - a.x;
    __int128 acy = (__int128)c.y - a.y;

    return abx * acy - aby * acx;
}

from shapely.geometry import MultiPoint

points = MultiPoint([
    (0, 0),
    (4, 0),
    (4, 4),
    (0, 4),
    (2, 2)
])

hull = points.convex_hull

print(hull)
print("凸包面积:", hull.area)
print("凸包周长:", hull.length)