题目描述
老洪来到了一个国家，这个国家有 $n$ 个村庄，第 $i$ 个村庄有一个奇妙的权值 $A_i$，以及另一个奇妙的权值 $B_i$。 其中 $B_i=\sum^i_{j=1}A_j$。 我们保证 $B_N = 0$。
现在老洪想要从任意一个村庄出发，遍历除起点外任意不少于 $1$ 个村庄，之后回到起始村庄。当老洪从第 $i$ 个村庄走到第 $j$ 个村庄的时候，老洪的收益是 $\frac{(A_i−A_j)B_iB_j}{2A_iA_j}$。
由于老洪的一些特殊爱好，假设老洪的遍历的村庄按照遍历顺序分别是$P_1,P_2,P_3,…,P_k,P_{k+1}$（当然，由于起始位置必须相同，这里 $P_{k+1}=P_1$），他希望存在一个 $2≤i≤k$，使得对于任意 $j<i$, 都满足 $B_{P_j}≤B_{P_{j+1}}$；而对于任意 $k≥j≥i$, 都满足$B_{P_j}≥B_{P_{j+1}}$。
换句话说，老洪想要自己经过的村庄的 $B$ 权值，在到达某个村庄之前是单调不降的，而之后又是单调不增的。
老洪希望你能算出他的最大收益。由于老洪没有spj，你需要对答案保留五位小数直接输出。
输入格式
对于每组测试数据，第一行一个整数 $N$，表示村庄个数。
接下来 $N$ 行每行 $1$ 个整数，数据第 $i+1$ 行的整数表示第 $i$ 个村庄的一个权值 $A_i$。另一个权值 $B_i$ 不会直接在输入中给出，但我们保证 $B_N = 0$。
##输出格式
对于每组测试数据，输出一行一个五位小数，表示答案保留五位小数之后的答案。
样例输入
10
1
4
1
2
-3
-5
2
-2
2
-2
样例输出
28.66667
数据规模
对于 $10 \%$ 的数据，$N≤7$。
对于 $20 \%$ 的数据，$N≤15$。
对于 $35 \%$ 的数据，$N≤20$。
对于 $50 \%$ 的数据，$N≤100$。
对于 $65 \%$ 的数据，$N≤1000$。
对于另外 $15 \%$ 的数据， $|Ai|=1$。
对于 $100 \%$ 的数据， $2≤N≤100000,0≤|Ai|≤100$。
题解
从 $i$ 到 $j$ 的收益可以转化为
$$
\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}
$$
将每个村庄 $i$ 看作点 $(\frac{B_i}{A_i}, B_i)$，这其实是点 $i$ 与 $j$ 组成的三角形面积
因为题目的要求，选取的点 $B$ 的值先单调不降的，而之后又是单调不增的，所以问题可以转化为求凸包后计算凸包的面积。
代码
#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;
}
inline int read(){
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(){
n = read();
for(register int i=1; i<=n; i++){
A[i] = read();
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;
}