Graham按极角排序但不用距离作为第二关键字会错的原因

P2742 [USACO5.1] 圈奶牛Fencing the Cows /【模板】二维凸包

补充一点,如果用叉积排序而不是用角度的话,选择基点时要在选最低点的同时尽量靠左,因为如果三点共线,叉积无法判断两个点的位置是在基点的同侧还是异侧,但这种情况在基点是最低点时只会在三点在同一水平线上时才会发生。
by Skeleton_Huo @ 2023-08-24 15:00:35


|