计算几何之凸包

计算几何之凸包

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

#define MAXN 100
struct Point {
    int x;
    int y;
};
Point points[MAXN + 1];
int stack[MAXN + 1];
bool visited[MAXN + 1];
int length;
// 向量叉积
// a是次顶的点，b是栈顶的点，c是待检查的点
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() {
    sort(points, cmp);
    int top1 = 0;
    stack[top1++] = 0;
    for (int i = 1; i < length; i++) {
        while (top1 > 1 && mul(points[stack[top1 - 2]], points[stack[top1 - 1]], points[i]) < 0){
            top1--;
            visited[stack[top1]] = false;
        }
        visited[i] = true;
        stack[top1++] = i;
    }
    int downSize = top1;
    for (int i = length - 2; i >= 0; i--) {
        if(visited[i])continue;
        while (top1 > downSize && mul(points[stack[top1 - 2]], points[stack[top1 - 1]], points[i]) < 0){
            top1--;
	    	visited[stack[top1]] = false;
        }
        visited[i] = true;
        stack[top1++] = i;
    }
    // 由于第一个点会被存放两次，因此我们要防止第一个点被重复放入
    for(int i = 0; i < top1 - 1; i++){
        ans.push_back(points[stack[i]]);
    }
}
int cmp(Point a, Point b) {
    if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}