简介

凸包的定义是能包含住所有点的凸多边形的交集，通过 Andrew 算法可以在 O(nlog⁡n)O(n\log n) 排序后用栈线性维护上下凸包，从而求出所有在凸包上的点，或者用平衡树动态维护凸包。

[USACO5.1] Fencing the Cows

给定 nn 个点，求凸包的周长。

数据范围：1≤n≤105,−106≤xi,yi≤1061\le n\le 10^5,-10^6\le x_i,y_i\le 10^6。

题目链接：P2742。

Andrew 算法的流程是对所有点以 x,yx,y 的字典序升序排序，这就保证了在 xx 相同时，正着遍历是 yy 递增的，逆序遍历是递减的，然后就可以用一个栈来维护这些凸包。

具体来说，当栈中有 ≥2\ge 2​ 个元素时，设栈顶为点 BB，栈顶下一个点为 AA，新加入元素为 CC，判断 ABAB 是否能被 ACAC 这条新边代替，如果能就弹出 BB​，直到无法代替为止。容易看出每个点至多入栈出栈一次，所以是线性的。

注意，如果 ABAB 与 ACAC 共线，同样要弹出 BB，保证在处理一段铅垂线时不会出现问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
const double eps = 1e-8;
int n;

int sgn(double x) {
    if (fabs(x) < eps) return 0;
    return x > 0 ? 1 : -1;
}

struct Vec {
    double x, y;

    bool operator<(const Vec& v) const {
        if (sgn(x - v.x)) return x < v.x;
        return sgn(y - v.y) < 0;
    }

    Vec operator-(const Vec& v) const {
        return {x - v.x, y - v.y};
    }

    double operator^(const Vec& v) const {
        return x * v.y - y * v.x;
    }

    double len() const {
        return sqrt(x*x + y*y);
    }
} p[N];

bool judge(int a, int b, int c) {
    return sgn(p[a] - p[b] ^ p[c] - p[b]) >= 0;
}

double andrew() {
    static int stk[N];
    double ans = 0;
    int tp = -1;
    sort(p+1, p+1+n);
    for (int i = 1; i <= n; i++) {
        while (tp > 0 && judge(stk[tp-1], stk[tp], i)) tp--;
        stk[++tp] = i;
    }
    for (; tp; tp--) ans += (p[stk[tp]] - p[stk[tp-1]]).len();

    tp = -1;
    for (int i = n; i; i--) {
        while (tp > 0 && judge(stk[tp-1], stk[tp], i)) tp--;
        stk[++tp] = i;
    }
    for (; tp; tp--) ans += (p[stk[tp]] - p[stk[tp-1]]).len();

    return ans;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lf%lf", &p[i].x, &p[i].y);
    return !printf("%.2lf\n", andrew());
}

[SHOI2012] 信用卡凸包

求 nn 个四角为 14\frac{1}{4}​ 圆弧的矩形，对于每个图形，矩形在处理前的边长为 w,hw,h，圆的半径为 rr，中心坐标为 xi,yix_i,y_i，逆时针旋转的弧度为 θi\theta_i，求这些图形构成的凸包的周长。

数据范围：1≤n≤1041\le n\le 10^4，1≤w,h,r≤1061\le w,h,r\le 10^6，−106≤xi,yi≤106-10^6\le x_i,y_i\le 10^6，0≤θi<2π0\le \theta_i\lt 2\pi。

题目链接：P3829。

如果画出这些图形，并且画出凸包，不难得出结论即每个圆心到凸包上的边做垂线，并且按照凸包的形状连接圆心，可以看出圆心构成的凸包与真正的凸包只差了一个圆。证明也很显然，转一圈方向改变了 2π2\pi，所以应该经过圆心角为 2π2\pi 的弧，也就是一个圆。

过 Qi(xi,yi)Q_i(x_i,y_i) 做出的直线 ll 倾斜角为 θi\theta_i，构造向量 ∣a⃗∣=w2−r,∣b⃗∣=h2−r|\vec{a}|=\frac{w}{2}-r,|\vec{b}|=\frac{h}{2}-r，方向分别与为 ll 的方向向量和法向量相同，那么圆心 PiP_i 的坐标就满足 PiQi⃗=a⃗+b⃗,a⃗−b⃗,−a⃗+b⃗,−a⃗−b⃗\vec{P_iQ_i}=\vec{a}+\vec{b},\vec{a}-\vec{b},-\vec{a}+\vec{b},-\vec{a}-\vec{b}。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
const double eps = 1e-8, pi = acos(-1);
int n;
double w, h, r, theta[N];

int sgn(double x) {
    if (fabs(x) < eps) return 0;
    return x > 0 ? 1 : -1;
}

struct Vec {
    double x, y;

    bool operator<(const Vec& v) const {
        if (sgn(x - v.x)) return x < v.x;
        return sgn(y - v.y) < 0;
    }

    Vec& operator*=(double k) {        
        x *= k, y *= k;
        return *this;
    }

    Vec operator+(const Vec& v) const {
        return {x + v.x, y + v.y};
    }

    Vec operator-(const Vec& v) const {
        return {x - v.x, y - v.y};
    }

    double operator^(const Vec& v) const {
        return x * v.y - y * v.x;
    }

    double len() const {
        return sqrt(x*x + y*y);
    }
} p[N<<2], q[N];

bool judge(int a, int b, int c) {
    return sgn(p[a] - p[b] ^ p[c] - p[b]) >= 0;
}

void getcircles() {
    int k = 0;
    for (int i = 1; i <= n; i++) {
        Vec a = {cos(theta[i]), sin(theta[i])}, b = {-a.y, a.x};
        a *= w/2 - r, b *= h/2 - r;
        p[++k] = q[i] + a + b;
        p[++k] = q[i] + a - b;
        p[++k] = q[i] - a + b;
        p[++k] = q[i] - a - b;
    }
}

double andrew() {
    static int stk[N<<2];
    double ans = 0;
    int tp = -1;
    n <<= 2;
    sort(p+1, p+1+n);
    for (int i = 1; i <= n; i++) {
        while (tp > 0 && judge(stk[tp-1], stk[tp], i)) tp--;
        stk[++tp] = i;
    }
    for (; tp; tp--) ans += (p[stk[tp]] - p[stk[tp-1]]).len();

    tp = -1;
    for (int i = n; i; i--) {
        while (tp > 0 && judge(stk[tp-1], stk[tp], i)) tp--;
        stk[++tp] = i;
    }
    for (; tp; tp--) ans += (p[stk[tp]] - p[stk[tp-1]]).len();

    return ans;
}

int main() {
    scanf("%d%lf%lf%lf", &n, &h, &w, &r);
    for (int i = 1; i <= n; i++) scanf("%lf%lf%lf", &q[i].x, &q[i].y, &theta[i]);
    getcircles();
    return !printf("%.2lf\n", andrew() + 2 * pi * r);
}

[HAOI2011] 防线修建

给定点 n,x,yn,x,y 表示 (0,0)(0,0)，(0,n)(0,n)，(x,y)(x,y) 初始三个点，再给 mm 个点 (xi,yi)(x_i,y_i)，初始所有点都在上凸包中。

接下来 qq 个操作，每个操作是在当前凸包删除一个点，或者查询当前凸包的周长。

数据范围：1≤m≤1051\le m\le 10^5，1≤q≤2×1051\le q\le 2\times 10^5，1≤n≤1041\le n\le 10^4。

题目链接：P2521。

删除是困难的，所以通过时间倒流大法可以让删除变成添加，这样我们需要操作的就是找到一个点的前驱和后继，需要用到平衡树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
using namespace std;

const int N = 200010;
const double eps = 1e-8;
int n, m, q;
bool del[N];

int sgn(double x) {
    if (fabs(x) < eps) return 0;
    return x > 0 ? 1 : -1;
}

struct Query {
    int typ, u;
} qry[N];

struct Vec {
    double x, y;
    bool lim;

    bool operator<(const Vec& v) const {
        if (x != v.x) return x < v.x;
        return y < v.y;
    }

    Vec operator-(const Vec& v) const {
        return {x - v.x, y - v.y};
    }

    double operator^(const Vec& v) const {
        return x * v.y - y * v.x;
    }
} p[N], val[N];

double len(Vec v) {
    return sqrt(1.0 * v.x * v.x + 1.0 * v.y * v.y);
}

set<Vec> s;
double now;

void upd(Vec a, Vec b, int fac) {
    if (a.lim || b.lim) return;
    now += fac * len(a-b);
}

bool judge(Vec a, Vec b, Vec c) {
    return sgn(a - b ^ c - b) <= 0;
}

void ins(Vec v) {
    s.insert(v);
    auto it = s.find(v), pre = prev(it), nxt = next(it);
    if (judge(*pre, *it, *nxt)) return s.erase(it), void();
    upd(*pre, *nxt, -1), upd(*pre, *it, 1), upd(*it, *nxt, 1);
    while (pre != s.begin()) {
        auto ppre = prev(pre);
        if (!judge(*ppre, *pre, *it)) break;
        upd(*ppre, *pre, -1), upd(*it, *pre, -1), upd(*ppre, *it, 1);
        s.erase(pre);
        pre = ppre;
    }
    while (nxt != prev(s.end())) {
        auto nnxt = next(nxt);
        if (!judge(*it, *nxt, *nnxt)) break;
        upd(*nnxt, *nxt, -1), upd(*it, *nxt, -1), upd(*nnxt, *it, 1);
        s.erase(nxt);
        nxt = nnxt;
    }
}

signed main() {
    int x, y;
    scanf("%d%d%d%d", &n, &x, &y, &m);
    for (int i = 1; i <= m; i++) scanf("%lf%lf", &p[i].x, &p[i].y);

    scanf("%d", &q);
    for (int i = 1; i <= q; i++) {
        scanf("%d", &qry[i].typ);
        if (qry[i].typ == 1) {
            scanf("%d", &qry[i].u);
            del[qry[i].u] = true;
        }
    }

    s.insert({-1e10, -1e100, true}), s.insert({1e10, -1e100, true});
    ins({0, 0}), ins({1.0 * n, 0}), ins({1.0 * x, 1.0 * y});
    for (int i = 1; i <= m; i++) if (!del[i]) ins(p[i]);

    static double stk[N];
    int tp = 0;
    for (int i = q; i; i--) {
        if (qry[i].typ == 1) ins(p[qry[i].u]);
        else stk[++tp] = now;
    }
    while (tp) printf("%.2lf\n", stk[tp--]);
    return 0;
}