二维凸包构造

标签：tmp return point double 构造 凸包 二维 凸壳

凸多边形是指所有内角大小都在 \([0,\pi]\) 范围内的 简单多边形
在平面上能包含所有给定点的最小凸多边形叫做凸包。

I.jarvis数学构造法

现在平面上有这么多个点。

1. 找到一条直线 \(l\) 过其中一点 \(A\) 并且所有其他点都在 \(l\) 的同侧，则 \(A\)必为凸包上的一点。
   
2. 让 \(l\) 以 \(A\) 为轴点向一个方向不断旋转，直到 \(l\) 碰到除 \(A\) 以外的第一个点(记为 \(B\))。
   
3. 再次以 \(B\) 为轴点，向相同的方向的旋转 \(l\)，重复上述过程，直到 \(l\) 回到 \(A\) 点。
   
4. 图形 \(ABCDEGI\) 即为一个凸包，同时这也是这个凸包的一个顶点序列。

struct point 
{
    double x;
    double y;
    point operator-(const point &p)
    {
        return (point){x-p.x,y-p.y};
    }
}p[KI];
stack<int>a;
point add(double x,double y)
{
    point s;
    s.x=x;
    s.y=y;
    return s;
}
double operator*(const point a,const point b)
{
    return a.x*b.y-b.x+a.y;
}
double clacd(point a,point b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
bool check(point a,point b,point c)
{
    double s=(b-a)*(c-a);
    return (s<0||(s==0 && clacd(b,a)>=clacd(c,a)))?true:false;
}
int main()
{
    int n=read();
    int cur=1;
    for(int i=1;i<=n;i++)
    {
        p[i].x=read();
        p[i].y=read();
        if(p[i].x<p[cur].x || p[i].x==p[cur].x && p[i].y<p[cur].y)
        {
            cur=i;
        }
    }
    a.push(cur);
    do
    {
        int et=1;
        for(int i=2;i<=n;i++)
        {
            if(check(p[a.top()],p[i],p[et]))
            {
                et=i;
            }
        }
        a.push(et);
    }while(a.top()!=cur);
    a.pop();
    cout<<a.size()<<'\n';
    stack<int>tmp;
    while(!a.empty())
    {
        tmp.push(a.top());
        a.pop();
    }
    while(!tmp.empty())
    {
        printf("%.2lf %.2lf\n",p[tmp.top()].x,p[tmp.top()].y);
        tmp.pop();
    }
    FINISH;
}

时间复杂度 \(\Theta(nm)\)。

II.Andrew构造法

首先把所有点以横坐标为第一关键字，纵坐标为第二关键字排序。
显然排序后最小的元素和最大的元素一定在凸包上。而且因为是凸多边形，我们如果从一个点出发逆时针走，轨迹总是“左拐”的，一旦出现右拐，就说明这一段不在凸包上。因此我们可以用一个单调栈来维护上下凸壳。
因为从左向右看，上下凸壳所旋转的方向不同，为了让单调栈起作用，我们首先 升序枚举 求出下凸壳，然后 降序 求出上凸壳。

标签：tmp,return,point,double,构造,凸包,二维,凸壳
From： https://www.cnblogs.com/SoN3ri/p/CCF_NMSL_CNMD_I_AK_CSP_NOIP_NOI_WC_CTSC_APIO_AND_IOI.html