计算几何之凸包
目录
计算几何之凸包
凸包的大概意思是,在点集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;
}
历史评论
开始评论