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

· · 题解

解决凸包，显然 Andrew 是非常优秀的算法，而我发现几乎大部分人都写的是极角排序，极角排序法虽然好像代码简单了一点，但是实现过程用了神奇的 atan2 等等处理，反而不如按坐标排序更直观而易于理解。

而题解中并没有找到一个写的清晰明了的按坐标排序的写法，因此，写一篇题解来补充这个漏洞。

证明略，不会的小伙伴可以去搜 Andrew 算法。

我们按照横坐标x从小到大排序，如果 x 相等按照纵坐标 y 从小到大排序，这步其实很关键，我们可以想到，如果到了下凸壳的最后几个点，而它们纵坐标相等，那么如果不是从小到大排序的y的话，就不能依次连起来从低到高上去了，而会删掉一些点，显然错误。

然后正着一遍找一个下凸壳，反着再来一遍找一个上凸壳，合起来就是一个凸包。

找的时候，每次选择将把当前点进栈，而满足凸壳需要将之前的点出栈，这里用向量叉乘可以很简单的判断出当前点是否方向正确，不正确的话出栈之前的点，换点继续判断方向。

（注意出栈不能把第一个点也出去了。）

然后就没啥了，写几个函数分别用来算向量，算叉乘，算距离，然后去找，找到把距离一加就 OK 了。

code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
struct point{
    double x,y;
}p[maxn]; 
inline point getvec(point a, point b){//我们英语都很棒，所以我们都知道vector是向量的意思。qwq
    return (point){(b.x-a.x),(b.y-a.y)};
}
inline double dis(point a,point b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
inline double xmul(point a,point b){
    return a.x*b.y-b.x*a.y;
}
inline bool operator < (const point &a,const point &b){
    if(a.x==b.x) return a.y<b.y;
    return a.x<b.x;
}
//上面的函数顾名思义就好了。
int n,stck[maxn];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%lf %lf",&p[i].x,&p[i].y);
    }
    sort(p+1,p+1+n);
    double ans=0;int cnt=0;
    stck[++cnt]=1,stck[++cnt]=2;
    for(int i=3;i<=n;i++){
        point u=getvec(p[stck[cnt-1]],p[stck[cnt]]);//根据连的起止点，算出它对应的向量的坐标。AB(X,Y)=B(x1,y1)-A(x2,y2);
        point v=getvec(p[stck[cnt]],p[i]);
        while(xmul(u,v)<0.0){//判断当前连边的方向。
            if(cnt==1) break;
            cnt--;
            u=getvec(p[stck[cnt-1]],p[stck[cnt]]);v=getvec(p[stck[cnt]],p[i]);
        }
        stck[++cnt]=i;
    }
    int tmp=cnt;
    stck[++cnt]=n,stck[++cnt]=n-1;
    for(int i=n-2;i>=1;i--){
        point u=getvec(p[stck[cnt-1]],p[stck[cnt]]);
        point v=getvec(p[stck[cnt]],p[i]);
        while(xmul(u,v)<0.0){
            if(cnt==tmp+1) break;
            cnt--;
            u=getvec(p[stck[cnt-1]],p[stck[cnt]]);v=getvec(p[stck[cnt]],p[i]);
        }
        stck[++cnt]=i;
    }
    for(int i=1;i<=cnt-1;i++){//其中会有两次n这个点，但是算距离的时候无所谓，自己到自己为0，如果需要输出一下这个凸包的各个点，那么就需要注意。
        ans+=dis(p[stck[i]],p[stck[i+1]]);
    }
    printf("%.2lf",ans);
    return 0;
}