计算几何之凸包

计算几何之凸包

凸包的大概意思是，在点集A中，选取子集a，将a中的点进行连线形成多边形（假若a中的点共线，则将多边形视为高度为0的长方形），则A中的点要么在多边形内部、要么在多边形上。

#define MAXN 100
struct Point {
    int x;
    int y;
};
Point points[MAXN + 1];
Point stack[MAXN + 1];
int length;
// 向量叉积
int mul(Point a, Point b, Point c) { return (b.x - a.x) * (c.y - b.y) - (c.x - b.x) * (b.y - a.y); }
void andrew() {
    int top1 = 0, top2;
    for (int i = 0; i < length; i++) {
       // 如果取 <= 则不包含共线情况、 < 则包含
        while (top1 > 1 && mul(stack[top1 - 2], stack[top1 - 1], points[i]) <= 0) top1--;
        stack[top1++] = points[i];
    }
    top2 = top1;
    for (int i = length - 1; i >= 0; i--) {
        while (top1 > top2 && mul(stack[top1 - 2], stack[top1 - 1], points[i]) <= 0) top1--;
        stack[top1++] = points[i];
    }
}
int cmp(Point a, Point b) {
    if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}