# [题解] ZROI 19省选1 终

##输出格式

## 样例输入

10
1
4
1
2
-3
-5
2
-2
2
-2


## 样例输出

28.66667


## 题解

\begin{aligned} \frac{(A_i−A_j)B_iB_j}{2A_iA_j} & = \frac{1}{2}B_iB_j(\frac{1}{A_j} – \frac{1}{A_i}) \\ &= \frac{1}{2}(\frac{B_j}{A_j}B_i – \frac{B_i}{A_i}B_j) \end{aligned}

## 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const long double eps = 1e-9;
const int MAXN = 100000 + 10;

struct Dot {
long double x, y;

Dot (){}
Dot (long double _x, long double _y){
x = _x;
y = _y;
}
};

int dcmp(long double x){
if(fabs(x) < eps)
return 0;

return x < 0 ? -1 : 1;
}

Dot operator + (Dot a, Dot b){
return Dot(a.x + b.x, a.y + b.y);
}

Dot operator - (Dot a, Dot b){
return Dot(a.x - b.x, a.y - b.y);
}

long double cro(Dot a, Dot b){
return a.x * b.y - a.y * b.x;
}

struct Polygon{
int n;
Dot p[MAXN];
}polygon;

long double area(Polygon x){
x.p[x.n + 1] = x.p[1];

long double ans = 0;

for(register int i=1; i<=x.n; i++){
ans += cro(x.p[i], x.p[i+1]);
}

return fabs(ans) / 2;
}

int x = 0;
int p = 1;
char ch = getchar();

while(ch < '0' || ch > '9'){
if(ch == '-')
p = 0;
ch = getchar();
}

while('0' <= ch && ch <= '9'){
x = x*10 + ch - '0';
ch = getchar();
}

return p ? x : (-x);
}

int n;
int A[MAXN], B[MAXN];

Dot dot[MAXN];
long double sx, sy;

inline bool cmp1(Dot a, Dot b){
if(dcmp(a.y - b.y) == 0)
return dcmp(a.x - b.x) < 0;

return dcmp(a.y - b.y) < 0;
}

inline bool cmp2(Dot a, Dot b){
long double aph1 = atan2(a.y - sy, a.x - sx);
long double aph2 = atan2(b.y - sy, b.x - sx);

if(dcmp(aph1 - aph2) == 0){
return dcmp(a.x - b.x) < 0;
}

return dcmp(aph1 - aph2) < 0;
}
int main(){

for(register int i=1; i<=n; i++){
B[i] = B[i-1] + A[i];
}

for(register int i=1; i<=n; i++){
dot[i] = (Dot){ (long double)B[i]/A[i], (long double)B[i]};
}

sort(dot+1, dot+n+1, cmp1);

polygon.p[1] = dot[1];
polygon.n = 1;

sx = dot[1].x;
sy = dot[1].y;

sort(dot+2, dot+n+1, cmp2);

for(register int i=2; i<=n; i++){
while(polygon.n > 1 && dcmp(cro(polygon.p[polygon.n] - polygon.p[polygon.n-1], dot[i] - polygon.p[polygon.n - 1])) <= 0)
polygon.n--;

polygon.p[++polygon.n] = dot[i];
}

long double ans = area(polygon);
printf("%.5Lf", ans);

return 0;

}