凸包

Posted on | In , ,

极角排序和Graham Scan法求凸包

极角排序

极角：向量和x轴正方向的形成的角。

Graham Scan法求凸包

凸包：凸包是把给定点包围在内部的、面积最小的凸多边形。

Scan法求凸包：在给定点集中找到y坐标最小的点，这个点一定是凸包上一点，那么所有点按照这个点极角排序，在凸包上的点满足这样的关系，即每个点都在凸包边的一侧。这样我们可以通过叉积，维护一个凸包集合不断进而求出凸包的集合。

时间复杂度：极角排序 $O(\rm nlogn)$，求凸包的过程是 $O(n)$ 的，所以算法整体的复杂度为 $O(\rm nlogn)$。

注意：对于凸包上共线的点，视情况舍取。

HDU1348 凸包模板题

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
const double PI=acos(-1.0);


int n,  tot;
double ans, r;

struct Point
{
    double x, y;
}p[maxn], P[maxn];

double xmul(Point A,Point B,Point C) { /// 叉积 ()
    return (B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y);
}
double dist(Point A,Point B){
    return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}

bool cmp(Point A, Point B) /// 极角排序
{
    double pp = xmul(p[1], A, B);
    if(pp>0) return true;
    if(pp<0) return false;
    return dist(p[1], A)<dist(p[1], B);
}

int main()
{
    int T;
    scanf("%d", &T);
    for(int cas=1;cas<=T;cas++)
    {
        if(cas!=1) printf("\n");
        scanf("%d%lf", &n, &r);
        ans=2*PI*r;
        for(int i=1;i<=n;i++)
        {
            scanf("%lf%lf", &p[i].x, &p[i].y);
        }
        if(n==1)
        {
            printf("%.0f\n", ans);
        }
        else if(n==2)
            printf("%.0f\n", ans+dist(p[1], p[2]));
        else
        {
            for(int i=1;i<=n;i++)
            {
                if(p[i].y<p[1].y)
                    swap(p[1], p[i]);
                else if(p[i].y==p[1].y && p[i].x<p[1].x)
                    swap(p[1], p[i]);
            }
            sort(p+2, p+n+1, cmp);
            P[1]=p[1];
            P[2]=p[2];
            tot=2;
            for(int i=3;i<=n;i++)
            {
                while(tot>1 && xmul(P[tot-1], P[tot], p[i])<=0) tot--;
                P[++tot]=p[i];
            }
            for(int i=1;i<tot;i++)
            {
                ans += dist(P[i+1],P[i]);
            }
            ans += dist(P[1], P[tot]);
            printf("%.0f\n", ans);
        }
    }
    return 0;
}