题解 P2742 【【模板】二维凸包 / [USACO5.1]圈奶牛Fencing the Cows】

· · 题解

更不好的阅读体验

凸包

一道模板题

首先凸包的定义:

用不严谨的话来讲，给定二维平面上的点集，凸包就是将最外层的点连接起来构成的凸多边形，它能包含点集中所有的点。

（百度百科给的解释）

因此以下就可以算是一个凸包

求法有两个

求法 1

第一个是把凸包分为上下两部分，对于下半部分不难发现斜率是在递增的，因此考虑先给所有点按照从左到右从下到上排序，然后类似于单调栈维护一个斜率。

然后伪代码大概就长这样

    for(i=1;i<=n;i++)
    {
        s[++size]=p[i];
        while(size>=3&&getk(s[size-2],s[size])<getk(s[size-2],s[size-1])) s[size-1]=s[size],size--;
    }
对于上半部分凸包，只需要从右向左枚举即可。 ### 求法2 上面的求法不需要高中数学功底~~因此可见只能解决较简单的问题~~对于比较毒瘤的问题，这样进一步写下去就很麻烦，所以考虑求法2 #### 就是Graham扫描法 首先前置芝士 #### 1.极角排序 这里只介绍按照atan2的方法。 `atan2(x,y)` 即返回$tan \alpha =\frac{x}{y}$ 的$\alpha$同时$\alpha \in [-\pi,\pi]

例如我们以左下角E(优先考虑最下)点对这些点极角排序，显然可见a

ABCDEFG的坐标：

7

-1.56 -1.11

1.68 -1.63

2.12 2.29

-2 1

-2.66 -3.87

2.46 -3.39

-4.7 -1.73

排序的结果是这样的（FBCADG)可以理解为从0度逆时针扫一圈。

atan2 （x,y）当y=0时，tan\alpha不存在 返回 0 但是x=0的时候返回-1

2.叉积

如图所示\vec p_1 * \vec p_2即为平行四边形面积

公式 \vec p_1 * \vec p_2 = x1y2-x2y1

原理可以参考下面这张出，出处大概在这里，由于图片加载太慢我放在图床上面了

同时四边形面积大于0说明p2在p1顺时针方向，如果==0重合，如果小于0就说明在逆时针方向

算叉积的时候可以用这个公式

(b_x-a_x)*(c_y-a_y)-(b_y-a_y)*(c_x-a_x) =(a_xb_y-b_xa_y)+(b_xc_y-c_xb_y)+(c_xa_y-a_xc_y) =\vec a*\vec b~+\vec b*\vec c ~+ \vec c*\vec a

c如果在a右边的话，\vec c*\vec a 面积就是小于0的

同理，如果上面的式子大于0，就说明c不在凸包里面。

如下图所示

刚开始d,b在栈里面，此时比较(d,c,b)，发现>0则c入栈

同理对于d，比较(b,d,c)也大于0，入栈

运行完毕，发现O\to b \to c \to d \to O就是凸包。

对于小于O的情况的解释：

例如 b,c,N三个点，按照极角排序，就是b,c,N,现在我们假设b,c在栈里面，就要比较(b,N,c),此时小于0，即c并不在凸包上（N取代了他的位置)

实际上推完了上面的东西，你就能写出来代码了.

#include<touwenjian.h>

using namespace std;

const double eps=1e-3;

int n,m,size;
double ans;

struct node{
    double x,y;
}p[200200],s[200200];

inline int cmp(node a,node b)
{
    double k1,k2;
    k1=atan2((a.y-p[1].y),(a.x-p[1].x));   
    k2=atan2((b.y-p[1].y),(b.x-p[1].x));
    if(k1!=k2) return k1<k2;
    return a.x<b.x;
}

inline double getdis(node a,node b)
{
    return sqrt(1.0*(a.x-b.x)*(a.x-b.x)+1.0*(a.y-b.y)*(a.y-b.y));  //上面讲的很清楚了 
}

inline double getcj(node a,node b,node c)
{
    return 1ll*(b.x-a.x)*(c.y-a.y)-1ll*(b.y-a.y)*(c.x-a.x);
}

inline int bj(node a,node b)
{
    return (a.y>b.y||(a.y==b.y)&&(a.x>b.x));
}

void gettb()
{
    p[0].x=p[0].y=0x3f3f3f3f;
    register int i,j;
    for(i=1;i<=n;i++)
    {
        if(bj(p[0],p[i])) p[0]=p[i],j=i;  //找到最小边的点，并且把他放到第一位 
    }
    swap(p[j],p[1]);
    sort(p+2,p+n+1,cmp);  //对后面的点极点排序 
    s[++size]=p[1];s[++size]=p[2];  //让前两个点入栈（他们一定是在凸包上） 
    for(i=3;i<=n;)
    {
        if(size>=2&&getcj(s[size-1],p[i],s[size])>=0) size--;  //就是上面说的 
        else s[++size]=p[i++];
    }
    s[0]=s[size];  //记得凸包要首尾相连 
    for(i=1;i<=size;i++) ans+=getdis(s[i-1],s[i]); //算距离即可 
}

int main()
{
    register int i,j;
    scanf("%d",&n);
    for(i=1;i<=n;i++) scanf("%lf %lf",&p[i].x,&p[i].y);
    gettb();
    printf("%.2lf",ans);
    return 0;
}