题解 | #小红的悬崖#

学习Andrew算法后突然想起这一题。

这简直就是为Andrew算法量身订做的模板题。

因为Andrew算法是一半一半求凸包，而这题实际上只需要求右半边的凸包即可。

甚至题目给出的点都是排好序的，我们就不用费力去排序以及求另一半凸包了。

```#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
//#define int long long
//#define LL long long
#define pdd pair<double,double>
#define endl "\n"
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define VI vector<int>
#define VVI vector<vector<int>>
#define PII pair<int,int>
#define MII map<int,int>
#define MSI map<string,int>
#define MAXN 0x3f3f3f3f
#define MINN -0x3f3f3f3f
#define Gheap priority_queue<int>
#define Lheap priority_queue<int,vector<int>,greater<int>>
using namespace std;
//const int N=1e6+100;
//int e[N],w[M],ne[M],h[M],idx;

bool cmp(pdd x,pdd y)
{
    return x.se!=y.se ? x.se<y.se : x.fi<y.fi;
}

double dis(pdd a,pdd b)
{
    return sqrt((a.fi-b.fi)*(a.fi-b.fi)+(a.se-b.se)*(a.se-b.se));
}

double cross(pdd a,pdd b,pdd c)
{
    return (b.fi-a.fi)*(c.se-a.se)-(b.se-a.se)*(c.fi-a.fi);
}

void solve()
{
    int n,a;
    double ans=0;
    cin>>n;
    pdd v[n+2];
    pdd st[4*n];
    int top=0;
    for(int i=0;i<=n;i++)
    {
        cin>>a;
        v[i]={a,i};
    }
    //sort(v,v+n+1,cmp);

    for(int i=0;i<=n;i++)
    {
        while(top>1&&cross(st[top-1],st[top],v[i])<=0) top--;
        st[++top]=v[i];
    }
    for(int i=2;i<=top;i++)
    {
        ans+=dis(st[i-1],st[i]);    
    }
    printf("%.12lf",ans);
}

/*简直就是Andrew算法的模板题*/
/*WA十几发原来是ans没有初始化为0...*/

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    //cin >> t;
    while(t--) solve();
}