计算几何之求凸包

给出平面上的一堆点，能够包住它的最小凸多边形就称为凸包。

求凸包有很多种算法，这里用的是安德鲁算法

它包含以下步骤：

将给定的点集合按照升序排列。x相同的话，按照y坐标升序排列
按照下列流程创建凸包的上部
- 将排序后的点按照x坐标从小到大的顺序加入凸包U。如果新加入的点使得U不再是凸多边形，那么就逆序删除之前已经插入U的点，直到U为凸多边形。
按照下列流程创建凸包的下部
- 将排序后的点按照x坐标从大到小的顺序加入凸包L。如果新加入的点使得L不再是凸多边形，那么就逆序删除之前已经插入L的点，直到L为凸多边形。

以点集U为例，如何判断加入点p之后的点集是否是凸包呢？

设将要加入p时，u的size是n，那么需要对向量(u[n-1]-u[n-1)和(p-u[n-2])进行叉乘，只要第二个向量位于第一个向量的逆时针处（也就是叉乘小于0），那么，此时p加入u，将会使得u不成为凸包，因此要删除最后加入的那个点。重复以上操作，直到加入p后，u仍然是凸包。

这里要注意的是，p严格位于前两个点组成的向量的逆时针方向时，才能删除前一个点！！！

题目：CGL_4_A

AC代码：

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

const double EPS = 1e-8;

#define MAXN 100005


class Point
{
public:
    double x, y;
    Point()
    {
    }
    Point(double x, double y)
    {
        (*this).x = x;
        (*this).y = y;
    }

    double operator^(const Point &p) const //叉乘
    {
        return x * p.y - y * p.x;
    }

    double operator*(const Point &p) const //点乘
    {
        return x * p.x + y * p.y;
    }

    Point operator*(const double &d) const
    {
        return Point(x * d, y * d);
    }

    Point operator/(const double &d) const
    {
        return Point(x / d, y / d);
    }

    Point operator-(const Point &p) const
    {
        return Point(x - p.x, y - p.y);
    }

    Point operator+(const Point &p) const
    {
        return Point(x + p.x, y + p.y);
    }

    double sqr()
    {
        return x * x + y * y;
    }
    double abs()
    {
        return sqrt(sqr());
    }

    double distance(const Point &p)
    {
        return fabs((*this - p).abs());
    }

    void print()
    {

        cout << x << ' ' << y << endl;
    }

    void read()
    {
        cin >> x >> y;
    }
};

class Line
{
public:
    Point p1, p2;
    Line();
    Line(Point p1, Point p2)
    {
        (*this).p1 = p1;
        (*this).p2 = p2;
    }
};

int n;

bool cmp(const Point &a, const Point &b)
{
    if (a.x < b.x)
        return true;
    else if (a.x > b.x)
        return false;
    else
    {
        if (a.y < b.y)
            return true;
        else
            return false;
    }
}

bool cmp2(const Point &a, const Point &b)
{
    if (a.y < b.y)
        return true;
    else if (a.y > b.y)
        return false;
    else
    {
        if (a.x < b.x)
            return true;
        else
            return false;
    }
}

bool is_counter_clockwise(Point a, Point b, Point p)//判断是否严格逆时针
{
    Point v1 = b - a;
    Point v2 = p - a;

    if ((v1 ^ v2) > EPS)
        return true;
    else
        return false;
}

vector<Point> andrewScan(vector<Point> s)
{
    vector<Point> u, l; //定义上凸包、下凸包的数组
    if (s.size() < 3)
        return s;

    sort(s.begin(), s.end(), cmp);

    //将x值最小的两个点依次放入u
    u.push_back(s[0]);
    u.push_back(s[1]);

    //将x值最大的两个点依次放入l
    l.push_back(s[s.size() - 1]);
    l.push_back(s[s.size() - 2]);

    //构建凸包上部
    unsigned ssize = s.size();

    for (int i = 2; i < ssize; ++i)
    {
        for (int j = u.size(); j >= 2 && (is_counter_clockwise(u[j - 2], u[j - 1], s[i])); --j)
        {
            u.pop_back();
        }

        u.push_back(s[i]);
    }

    //构建凸包下部
    for (int i = ssize - 3; i >= 0; --i)
    {
        for (int j = l.size(); j >= 2 && (is_counter_clockwise(l[j - 2], l[j - 1], s[i])); --j)
        {
            l.pop_back();
        }
        l.push_back(s[i]);
    }

    //逆时针方向存储点的序列
    reverse(l.begin(), l.end());

    for (int i = u.size() - 2; i >= 1; --i)
        l.push_back(u[i]);

    return l;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    vector<Point> p;

    for (int i = 0; i < n; ++i)
    {
        Point tmp;
        tmp.read();
        p.push_back(tmp);
    }
    vector<Point> ans = andrewScan(p);

    int ans_size = ans.size();
    cout << ans_size << endl;

    // for(auto x:ans)
    //   x.print();

    vector<Point> tmpp;
    for (Point x : ans)
        tmpp.push_back(x);

    sort(tmpp.begin(), tmpp.end(), cmp2);

    int idx = 0;
    for(;idx<ans_size;++idx)
    {
        if(ans[idx].x==tmpp[0].x&&ans[idx].y==tmpp[0].y)
        {
            break;
        }
    }

    for(int i=0;i<ans_size;++i)
    {
        ans[(i+idx)%ans_size].print();
    }
}

转载请注明来源：https://www.longjin666.top/?p=835

欢迎关注我的公众号“灯珑”，让我们一起了解更多的事物~