Skip to content

二维凸包

Graham

先找出 \(y\) 坐标最小的点，作为 \(p_1\)

然后将 \(p_2\cdots p_n\) 进行极角排序

维护一个栈 \(s\), 初始时将前两个点 \(p_1, p_2\) 加入栈

这个栈相当于维护了一个凸壳

每次考虑一个点 \(p_i\), 建立两条边 \((s_{top-1},s_{top}),(s_{top}, p_i)\), 如果两条边叉积小于零，说明夹角是顺时针方向的，即第二条边相对于第一条边向外拐，那么这就使得当前这个凸壳凹了，那么就将中间的凹点去掉，即将栈顶弹出，循环判断直到凸，然后入栈新节点

最后的凸壳就是凸包，直接计算距离

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int T, n, top;
struct node
{
    double x, y;
} p[N], stk[N];
double check(node a1, node a2, node b1, node b2)
{
    double x1 = (a2.x - a1.x), y1 = (a2.y - a1.y);
    double x2 = (b2.x - b1.x), y2 = (b2.y - b1.y);
    return x1 * y2 - x2 * y1;
}
double dis(node a, node b)
{
    double x = b.x - a.x, y = b.y - a.y;
    return sqrt(x * x + y * y);
}
bool cmp(node a, node b)
{
    double tmp = check(p[1], a, p[1], b);
    if (tmp > 0)
        return 1;
    else if (tmp < 0)
        return 0;
    else
        return (dis(p[0], a) < dis(p[0], b));
}
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        scanf("%lf%lf", &p[i].x, &p[i].y);
        if (i != 1 && p[i].y < p[1].y)
            swap(p[1], p[i]);
    }
    sort(p + 2, p + n + 1, cmp);
    stk[1] = p[1];
    top = 1;
    for (int i = 2; i <= n; ++i)
    {
        while (top > 1 && check(stk[top - 1], stk[top], stk[top], p[i]) < 0)
            --top;
        stk[++top] = p[i];
    }
    stk[++top] = p[1];
    double ans = 0;
    for (int i = 2; i <= top; ++i)
    {
        ans += dis(stk[i - 1], stk[i]);
    }
    printf("%.2lf\n", ans);
}
int main()
{
    solve();
    return 0;
}

Andrew

按照 \(x\) 坐标排序，其他一样

我们发现从 \(x\) 坐标最小的点向右考虑，求出的是一个下凸壳，而不是整个凸包

所以在从右到左求一个上凸壳，两者合并即可

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int T, n, top, cnt;
struct node
{
    double x, y;
} p[N], stk[N], ans[N];
double check(node a1, node a2, node b1, node b2)
{
    double x1 = (a2.x - a1.x), y1 = (a2.y - a1.y);
    double x2 = (b2.x - b1.x), y2 = (b2.y - b1.y);
    return x1 * y2 - x2 * y1;
}
double dis(node a, node b)
{
    double x = b.x - a.x, y = b.y - a.y;
    return sqrt(x * x + y * y);
}
bool cmp(node a, node b)
{
    return a.x == b.x ? a.y < b.y : a.x < b.x;
}
bool CMP(node a, node b)
{
    return a.x == b.x ? a.y > b.y : a.x > b.x;
}
void solve()
{
    cin >> n;

    for (int i = 1; i <= n; ++i)
    {
        scanf("%lf%lf", &p[i].x, &p[i].y);
    }
    sort(p + 1, p + n + 1, cmp);
    stk[1] = p[1];
    top = 1;
    for (int i = 2; i <= n; ++i)
    {
        while (top > 1 && check(stk[top - 1], stk[top], stk[top], p[i]) < 0)
            --top;
        stk[++top] = p[i];
    }

    sort(p + 1, p + n + 1, CMP);
    cnt = top - 1;
    for (int i = 2; i <= n; ++i)
    {
        while (top > cnt + 1 && check(stk[top - 1], stk[top], stk[top], p[i]) < 0)
            --top;
        stk[++top] = p[i];
    }
    double ans = 0;
    for (int i = 2; i <= top; ++i)
    {
        ans += dis(stk[i - 1], stk[i]);
    }
    printf("%.2lf\n", ans);
}
int main()
{
    solve();
    return 0;
}

旋转卡壳

用来求凸包直径

枚举每一条边，求出距离这条边最远的点

由于边逆时针旋转的时候，最远的点必定只会逆时针旋转，不会顺时针(可以想想为什么)

那么点也是单向旋转，就可以用一个指针 \(O(n)\) 维护这个点，求出答案

注意写的时候，只要高度 不减 就应该继续换点，而不是只有高度 增 才换点

考虑这样的情况：

7
0 0
1 0
2 0
3 0
4 2
5 4
3 6

从 \(1, 2\) 号点开始，后面的 \(3, 4\) 号点高度都不减，所以应该继续换点直到最高的 \(7\) 号点；但是如果不增就停止，那么 \(7\) 号点就算不到了

这导致答案变成 40, 而实际应该为 45

并且每次换点都可以求一次答案, 防止漏解

还有一个坑，如果凸包是一条线，那么所有高度都为 \(0\), 会死循环，所以判断转一圈后就强制停止

#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int N = 2e5 + 10;
int T, n, top, cnt;
struct node
{
    int x, y;
} p[N], stk[N];
int check(node a1, node a2, node b1, node b2)
{
    int x1 = (a2.x - a1.x), y1 = (a2.y - a1.y);
    int x2 = (b2.x - b1.x), y2 = (b2.y - b1.y);
    return x1 * y2 - x2 * y1;
}
int dis(node a, node b)
{
    int x = b.x - a.x, y = b.y - a.y;
    return x * x + y * y;
}
int height(node a, node b, node x)
{
    int x1 = x.x - a.x, y1 = x.y - a.y;
    int x2 = b.x - a.x, y2 = b.y - a.y;
    return x1 * x1 + y1 * y1 - (x1 * x2 + y1 * y2) * (x1 * x2 + y1 * y2) / (x2 * x2 + y2 * y2);
}
bool cmp(node a, node b)
{
    return a.x == b.x ? a.y < b.y : a.x < b.x;
}
bool CMP(node a, node b)
{
    return a.x == b.x ? a.y > b.y : a.x > b.x;
}
void Andrew()
{
    sort(p + 1, p + n + 1, cmp);
    stk[1] = p[1];
    top = 1;
    for (int i = 2; i <= n; ++i)
    {
        while (top > 1 && check(stk[top - 1], stk[top], stk[top], p[i]) < 0)
            --top;
        stk[++top] = p[i];
    }
    sort(p + 1, p + n + 1, CMP);
    cnt = top - 1;
    for (int i = 2; i <= n; ++i)
    {
        while (top > cnt + 1 && check(stk[top - 1], stk[top], stk[top], p[i]) < 0)
            --top;
        stk[++top] = p[i];
    }
}
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        scanf("%lld%lld", &p[i].x, &p[i].y);
    }
    Andrew();
    int l = 2;
    int ans = 0;
    for (int i = 2; i <= top; ++i)
    {
        node a = stk[i - 1], b = stk[i];
        int d = height(a, b, stk[l]);
        int start = l;
        while (1)
        {
            ans = max(ans, max(dis(a, stk[l]), dis(b, stk[l])));
            int r = l % (top) + 1;
            if (height(a, b, stk[r]) < d || r == start){ // note this
                break;
            }else l = r, d = height(a, b, stk[r]);
        }
    }
    printf("%lld\n", ans);
}
signed main()
{
    solve();
    return 0;
}