【算法设计与分析 李春葆】计算几何（二）——求解凸包问题

凸多边形以及凹多边形的区别：

1. 凸多边形没有凹陷处，但是凹多边形至少有一个凹陷处。
2. 凸多边形任意两点均在内部，但是凹多边形至少有一对点，他们的连线在多边形外部。
3. 沿着凸多边形的转向是相同的，而沿着凹多边形的转向有不同的地方，这个地方正是凹点。

点集的凸包

定义：在平面上能包含所有给定点的最小凸多边形叫做凸包。

形象理解：礼品包裹法

性质：是包含所有的点的多边形中周长最小的

礼品包裹法

时间复杂度：\(O(nh)\)，n为所有的点，h为凸包上的点。

这种算法只是玩一玩。

思路：找边界的一个点（最左边，如果有多个是相同的，那么就取最下面）

然后过这一个点做射线逆时针旋转，找到第一个碰到的点，这一个点也加入凸包中

这里不太想实现，太low了。

Graham 扫描算法

[USACO5.1]圈奶牛Fencing the Cows /【模板】二维凸包（洛谷）

题目描述

农夫约翰想要建造一个围栏用来围住他的奶牛，可是他资金匮乏。他建造的围栏必须包括他的奶牛喜欢吃草的所有地点。对于给出的这些地点的坐标，计算最短的能够围住这些点的围栏的长度。

输入格式

输入数据的第一行是一个整数。表示农夫约翰想要围住的放牧点的数目 \(n\)。

第 \(2\) 到第 \((n + 1)\) 行，每行两个实数，第 \((i + 1)\) 行的实数 \(x_i, y_i\) 分别代表第 \(i\) 个放牧点的横纵坐标。

输出格式

输出输出一行一个四舍五入保留两位小数的实数，代表围栏的长度。

输入

4
4 8
4 12
5 9.3
7 8

输出

12.00

提示

数据规模与约定：

对于 \(100\%\) 的数据，保证 \(1 \leq n \leq 10^5\)，\(-10^6 \leq x_i, y_i \leq 10^6\)。小数点后最多有 \(2\) 位数字。

废话不说，直接上代码：

鉴于原题是毒瘤题，所以除了前两个可以过就行了

#include <bits/stdc++.h>
using namespace std;
#define N 100020

class Point{
    public:
    double x, y;
    Point(){};
    Point(double x1, double y1){
        x = x1;
        y = y1;
    }
    void disp(){
        printf("(%g, %g)", x, y);
    }
};
int n;
Point a[N];
Point stac[N];
int top = 0;
Point operator -(const Point &p1, const Point &p2){
    return Point(p1.x - p2.x, p1.y - p2.y);
}

double Det(const Point &p1, const Point &p2){
    return p1.x*p2.y-p1.y*p2.x;
}

int Direction(const Point &p0, const Point &p1, const Point &p2)
{
    double d = Det(p1-p0, p2-p0);
    if(d > 0) return 1;
    else if(d == 0) return 0;
    else return -1;
}
bool cmp(const Point &p1, const Point &p2)
{
    return Direction(a[1], p1, p2) > 0;
}

double Distance(const Point &p1, const Point &p2)
{
    Point t = p1-p2;
    return sqrt(t.x*t.x + t.y*t.y);
}


void solve()
{
    int pos = -1;
    for(int i = 1; i <= n; i++)
    {
        if(pos == -1 || a[i].y < a[pos].y || a[i].y == a[pos].y && a[i].x < a[pos].x)
            pos = i;
    }
    swap(a[1], a[pos]);
    sort(a+2, a+1+n, cmp);
    for(int i = 1; i <= n; i++) a[i].disp();
    stac[++top] = a[1];
    stac[++top] = a[2];
    stac[++top] = a[3];

    for(int i = 4; i <= n; i++)
    {
        while(top >= 2 && ( Direction(stac[top-1], stac[top], a[i]) < 0  ||
                            Direction(stac[top-1], stac[top], a[i]) == 0 && 
                            Distance(stac[top-1], a[i]) > Distance(stac[top-1], stac[top]))
                          )
        {
            top --;
        }
        stac[++top] = a[i];
    }
}
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        double x, y;
        scanf("%lf%lf",&x, &y);
        a[i] = Point(x, y);
    }
    solve();
    //for(int i = 1; i <= top; i++) stac[i].disp();
    double ans = 0.0;
    for(int i = 1; i <= top - 1; i++)
    {
        ans += Distance(stac[i], stac[i+1]);
    }
    ans += Distance(stac[1], stac[top]);
    printf("%.2lf", ans);
    return 0;
}

这一个算法的时间复杂度是\(nlogn\)（排序的时间）

Andrew 算法求凸包

这一个算法的时间复杂度是\(nlogn\)（瓶颈也在排序的时间）