Lua凸包入门：包住所有点的边界

-- 错误：逐对点连线的暴力枚举，规模一大就崩
for i = 1, #pts do
    for j = 1, #pts do
        checkEdge(pts[i], pts[j])
    end
end

local function cross(o, a, b)
    return (a[1] - o[1]) * (b[2] - o[2])
        - (a[2] - o[2]) * (b[1] - o[1])
end
local function hull(points)
    table.sort(points)
    local st = {}
    for _, p in ipairs(points) do
        while #st >= 2
            and cross(st[#st - 1], st[#st], p) <= 0 do
            st[#st] = nil
        end
        st[#st + 1] = p
    end
    local t = #st + 1
    for i = #points, 1, -1 do
        while #st >= t
            and cross(st[#st - 1], st[#st], points[i]) <= 0 do
            st[#st] = nil
        end
        st[#st + 1] = points[i]
    end
    return st
end