brz的序列

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+7;
int a[N];
struct node{
    double x, y;
}p[N],s[N];
int n;
bool cmp(node a, node b)
{
    if(a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}
bool Cross(node a, node b, node c)
{
    double x1 = a.x - b.x, y1 = a.y - b.y;
    double x2 = c.x - b.x, y2 = c.y - b.y;
    if((x1*y2-x2*y1) < 0) return 0;
    return 1;
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 1; i <= n; i++) {
        scanf("%d",&a[i]);
        p[i].x = i, p[i].y = 1.0*a[i];
    }
    if(n == 1) {
        printf("%.10f\n",p[1].y); return 0;
    }
    else if(n == 2) {
        printf("%.10f\n",p[1].y+p[2].y); return 0;
    }
    sort(p+1, p+n+1, cmp);
    int num = 0;
    for(int i = 1; i <= n; i++)
    {
        while(num >= 2 && !Cross(s[num], s[num-1],p[i]))
            num--;
        s[++num] = p[i];
    }
    s[0].x = 0, s[0].y = 0;
    double ans = 0.0;
    for(int i = 2; i <= num; i++)
        ans += 1.0*(s[i].y + s[i-1].y) * (s[i].x - s[i-1].x + 1) / 2.0 - s[i].y;
    ans += s[num].y;
    printf("%.10f\n",ans);
}