Graham扫描算法点排序疑问：LeetCode Erect The Fence实现问题

基准点选择（你的做法没问题） #

固定选最左下的点：Y坐标最小的点，Y相同则取X最小的点。

核心排序规则（解决你的共线点问题） #

所有其他点按以下优先级排序：

1. 按相对于基准点的极角从小到大：用叉积判断，叉积为负说明点在基准点左侧（极角更小），叉积为正则在右侧；叉积为0表示共线。
2. 极角相同时，按到基准点的距离从近到远排序：
   • 这是解决你遇到的同X不同Y点错误的关键。《Erect The Fence》要求保留所有凸包边界上的点，而非仅凸包顶点。按近到远排序，共线点会被依次入栈，不会被错误弹出，最终全部保留在结果中。

你的原排序错误原因 #

你之前用“角度相同时Y降序、X升序”，本质是把离基准点远的共线点排在前面。比如基准点(0,0)，共线点(1,1)、(2,2)，先处理(2,2)入栈，再处理(1,1)时，叉积为0，栈顶的(2,2)会被判定为“非左转”弹出，导致(2,2)丢失——但这两个点都属于凸包边界，必须保留。

关于半区划分的疑问 #

“按最下点与最高点连线划分半区排序”不是标准Graham扫描的逻辑，完全没必要。标准算法只需基于基准点的极角+距离排序，额外划分半区只会增加复杂度，容易引入新错误。

实用排序代码示例（伪代码） #

用叉积避免浮点误差的排序逻辑：

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

# o是选好的最左下基准点
points.sort(key=lambda p: (
    cross(o, p, (o[0]+1, o[1])),  # 以基准点右侧水平线为参照排序极角
    (p[0]-o[0])**2 + (p[1]-o[1])**2  # 用距离平方替代距离，避免开根号
))

或者用自定义比较函数（Python3需配合functools.cmp_to_key）：

from functools import cmp_to_key

def compare(a, b):
    cp = cross(o, a, b)
    if cp != 0:
        return -cp  # 叉积为正，a极角更小，排前面
    # 共线时按距离近到远排序
    dist_a = (a[0]-o[0])**2 + (a[1]-o[1])**2
    dist_b = (b[0]-o[0])**2 + (b[1]-o[1])**2
    return dist_a - dist_b

points.sort(key=cmp_to_key(compare))

内容的提问来源于stack exchange，提问作者Szyszka947