凸包¶

算法Andrew

对所有点按坐标×为第一关键字、 y 为第二关键字排序。第 1 、第 n 两个点一定在凸包上。

struct node{
    int x,y;
}p[N];

bool cmp(node x,node y){
    if(x.x==y.x)return x.y<y.y;
    return x.x<y.x;
}

signed main(){

//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
//  freopen(".txt","w",stderr);
    n=rd;
    for(int i=1;i<=n;i++){
        p[i].x=rd;
        p[i].y=rd;
    }

    sort(p+1,p+n+1,cmp);
}

2 ，先顺序枚举所有点，求下凸包。

用栈维护当前在凸包上的点：新点入栈前，总要判断该弹出哪些旧占只要新点处在由栈顶两点构成的有向直线的右侧或共线，就弹出旧点。不能弹出时，新点入栈。

那么我们怎么样判断新点是否处在由栈顶两点构成的有向直线的右侧或共线呢？我们可以计算原点a→b和新点b→c两条有向线段的叉积。如果叉积≤0，则说明在右侧或者共线。

double cross(node a,node b,node c){
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

3 ．再逆序枚举所有点，求上凸包。用栈维护同上。

注意：每个点入栈两次，出栈不超过两次所以总次数不超过4n

void andrew(){
    for(int i=1;i<=n;i++){
        while(top>1&&cross(stk[top-1],stk[top],p[i])<=0)top--;
        stk[++top]=p[i];

    }
    int t=top;
    for(int i=n-1;i;i--){//注意这里用n-1防止n点重复入栈
        while(top>t&&cross(stk[top-1],stk[top],p[i])<=0)top--;
        stk[++top]=p[i];
    }
}

算法结束后每个点会在栈中一次，但是1号点会出现两次。反正就是知道把i→i+1连接起来更好是完整的周长就行了。

COde

/*////////ACACACACACACAC///////////
       . Coding by Ntsc .
       . FancyKnowledge .
       . Prove Yourself .
/*////////ACACACACACACAC///////////

//
#include<bits/stdc++.h>

//
#define int long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define err(fmt, ...) fprintf(stderr, "[%d] : " fmt "\n", __LINE__, ##__VA_ARGS__)
///*
#define pr pair<double,int>
#define pf first
#define ps second
#define pb push_back
//*/

//
using namespace std;



#define rd read()
inline int read() {
    int xx = 0, ff = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            ff = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') xx = xx * 10 + (ch - '0'), ch = getchar();
    return xx * ff;
}
inline void write(int out) {
    if (out < 0)
        putchar('-'), out = -out;
    if (out > 9)
        write(out / 10);
    putchar(out % 10 + '0');
}
//
const int N=2e5+5;
const int M=1e3;
const int MOD=1e9+7;
const int MMOD=903250223;
const int INF=1e9;
const int IINF=1e18;
const db eps=1e-9;
//


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

int n,m,q,d[N],k,idx,len[N],res,tmp,cnt[N],id[N];
double ans;

node stk[N];
int top;

bool cmp(node x,node y){
    if(x.x==y.x)return x.y<y.y;
    return x.x<y.x;
}

double cross(node a,node b,node c){
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

double dis(node a,node b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

void andrew(){
    for(int i=1;i<=n;i++){
        while(top>1&&cross(stk[top-1],stk[top],p[i])<=0)top--;
        stk[++top]=p[i];

    }
    int t=top;
    for(int i=n-1;i;i--){
        while(top>t&&cross(stk[top-1],stk[top],p[i])<=0)top--;
        stk[++top]=p[i];
    }
}

signed main(){

//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
//  freopen(".txt","w",stderr);
    n=rd;
    for(int i=1;i<=n;i++){
        cin>>p[i].x>> p[i].y;
    }

    sort(p+1,p+n+1,cmp);

    andrew();

    for(int i=1;i<top;i++)ans+=dis(stk[i],stk[i+1]);

    printf("%.2lf",ans);
    return 0;
}

//check your long long and the size of memery!!!