gcmp::Vector2d 问题 使用Melkman 求凸包

使用GaoCp Math Package中的Vector2d向量库以及Melkman算法来求凸包，以下是示例代码：

#include <bits/stdc++.h>
#include <gcmp.hpp>

using namespace std;
using namespace gcmp;

const int N = 1e5 + 5;

int n, top;
Vector2d p[N], q[N], stk[N];

void melkman() {
    int front = 1, back = 1;
    stk[1] = q[1];
    for (int i = 2; i <= n; ++i) {
        // 加入左侧的点
        if (q[i].x > stk[front].x) {
            stk[--front] = q[i];
        } else if (q[i].x < stk[front].x) {
            stk[++front] = q[i];
        } else {
            stk[front] = q[i];
        }
        // 加入右侧的点
        if (q[n - i + 1].x > stk[back].x) {
            stk[++back] = q[n - i + 1];
        } else if (q[n - i + 1].x < stk[back].x) {
            stk[--back] = q[n - i + 1];
        } else {
            stk[back] = q[n - i + 1];
        }
    }
    top = 0;
    for (int i = front; i <= back; ++i) {
        stk[++top] = stk[i];
    }
}

bool cmp(Vector2d a, Vector2d b) {
    double c = a.x - b.x;
    if (c == 0) return a.y < b.y;
    return c < 0;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%lf%lf", &p[i].x, &p[i].y);
    }
    sort(p + 1, p + n + 1, cmp);
    int k = 0;
    for (int i = 1; i <= n; ++i) {
        while (k > 1 && (p[i] - q[k - 1]).cross(q[k] - q[k - 1]) <= 0) {
            --k;
        }
        q[++k] = p[i];
    }
    int t = k;
    for (int i = n - 1; i >= 1; --i) {
        while (k > t && (p[i] - q[k - 1]).cross(q[k] - q[k - 1]) <= 0) {
            --k;
        }
        q[++k] = p[i];
    }
    melkman();
    for (int i = 1; i <= top; ++i) {
        printf("%.0f %.0f\n", stk[i].x, stk[i].y);
    }
    return 0;
}

这段代码使用了GaoCp Math Package中的Vector2d向量库和Melkman算法来求凸包。具体思路可以参考以下步骤：

1. 将所有点按横坐标排序。
2. 对排序后的点依次进行半平面交，得到凸包的上下两个部分。
3. 对上下两个部分使用Melkman算法进行合并。
4. 最后得到的栈中就是凸包的所有点。

需要注意的是，在使用Melkman算法进行合并时，需要分别从左至右和从右至左两次进行，最后将结果合并。

希望对你有所帮助！