二维凸包

luogu模板传送门：https://www.luogu.org/problem/P2742

二维凸包就是下面这种东西：手动画图

如果你还不知道是什么，看下面：

再不懂我也没办法了，我一语文渣......

重点是这玩意怎么维护，手玩发现不让计算的话简直不能再简单，交给计算机的话告诉我哪几个点什么都给你算出来

要学的就是怎么找到凸包上的那些点集

书上好像写了三种做法，我只写写我喜欢(hui)的

Graham算法：

步骤就是你先找一个最低点，然后把这个点之外的所有点排个序（如何实现排序下面再说），排完序之后你再按逆时针扫一遍，发现哪个点不满足条件就弹出。

以上内容胡诌

我还是手画个图吧

数字为排完序的顺序，你如何排序呢？

运用矢量积！！！

一个点Pa，另一个点Pb，基准点P0

当（Pa-P0）x（Pb-P0）<0  那么 Pa在Pb的逆时针方向

反之在Pb的顺时针方向（或同一条直线）。

排完序后呢？

现在你要考虑3号点，我们看着显然比2号点优对吧

发现31矢量 X 21矢量 >0

所以当（i - [top-1]）X （[top] - [top-1]）>0 那么top--;

#include<cstdio>
#include<algorithm>
#include<cmath>
#define R register
using namespace std;
int n,di=0;
double ans;
struct ddd{
    double x,y;
    ddd operator -(ddd &b){
        return (ddd){x-b.x,y-b.y};
    }
}p[10100];
double operator * (ddd a,ddd b){
    return a.x*b.y-a.y*b.x;
}
double dis(ddd a,ddd b){
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); 
}
inline bool com(ddd a,ddd b){
    double s=(a-p[1])*(b-p[1]);
    return(s>0||(s==0&&dis(a,p[1])>=dis(b,p[1])));
}
int stac[10100],top;
inline bool oleft(int p0,int now,int did){
    double s=(p[now]-p[p0])*(p[did]-p[p0]);
    return s>0||(s==0&&dis(p[now],p[p0])>=dis(p[did],p[p0]));
}
int main (){
    scanf("%d",&n);
    p[0].y=1e9;
    for(R int i=1;i<=n;i++){
        scanf("%lf%lf",&p[i].x,&p[i].y);
        if(p[i].y<p[di].y) di=i;
        else if(p[i].y==p[di].y&&p[i].x<p[di].x) di=i;
    }
    swap(p[1],p[di]);
    di=1;p[++n]=p[1];
    sort(p+2,p+1+n,com);
    stac[++top]=1;
    stac[++top]=2;
    for(R int i=3;i<=n;i++){
        while(top>1&&oleft(stac[top-1],i,stac[top])) top--;
        stac[++top]=i;
    }
    for(R int i=1;i<top;i++){
        ans+=sqrt(dis(p[stac[i+1]],p[stac[i]]));
    }
    printf("%.2lf\n",ans);
    return 0;
}

View Code