凸包

叉积

Convex Hull

1. sort the points in horizontal order
   use Monotonic Stack and Cross Product scan twice
   No precision Error
   https://github.com/wwwwodddd/Zukunft/blob/master/luogu/P2742.cpp

2. sort the points in argular order
   choose the bottom left one, calculate the angle
   use Monotonic Stack and Cross Product scan one

We can do binary search on the convex hull

动态凸包

Never seen in USACO

use two sets to maintain the points of upper/lower convex hull

https://codeforces.com/problemsets/acmsguru/problem/99999/277

Volume of a Parallelepiped

P5155 [USACO18DEC]Balance Beam P

https://www.luogu.com.cn/problem/P5155

题目描述

Bessie为了存钱给她的牛棚新建一间隔间，开始在当地的马戏团里表演，通过在平衡木上小心地来回走动来展示她卓越的平衡能力。

Bessie能够通过表演赚到的钱取决于她最终成功跳下平衡木的位置。平衡木上从左向右的位置记为 $0,1,\ldots,N+1$ 。如果Bessie到达了位置 $0$ 或是 $N+1$ ，她就会从平衡木的一端掉下去，遗憾地得不到报酬。

如果Bessie处在一个给定的位置 $k$ ，她可以进行下面两项中的任意一项：

1. 投掷一枚硬币。如果背面朝上，她前往位置 $k-1$ ，如果正面朝上，她前往位置 $k+1$ （也就是说，每种可能性 $1/2$ 的概率）。

2. 跳下平衡木，获得 $f(k)$ 的报酬（ $0 \leq f(k) \leq 10^9$ ）。

Bessie意识到她并不能保证结果能够得到某一特定数量的报酬，这是由于她的移动是由随机的掷硬币结果控制。然而，基于她的起始位置，她想要求出当她进行一系列最优的决定之后，她能够得到的期望报酬（“最优”指的是这些决定能够带来最高可能的期望报酬）。

例如，如果她的策略能够使她以 $1/2$ 的概率获得 $10$ 的报酬，$1/4$ 的概率获得 $8$ 的报酬，$1/4$ 的概率获得 $0$ 的报酬，那么她的期望报酬为加权平均值 $10 \times (1/2)+8 \times (1/4)+0 \times (1/4)=7$ 。

输入格式

输入的第一行包含 $N$ （ $2 \leq N \leq 10^5$ ）。以下 $N$ 行包含 $f(1) \ldots f(N)$ 。

输出格式

输出 $N$ 行。第 $i$ 行输出 $10^5$ 乘以Bessie从位置 $i$ 开始使用最优策略能够获得的报酬的期望值，向下取整。

样例 #1

样例输入 #1

2
1
3

样例输出 #1

150000
300000

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
int n;
double a[100020];
int s[100020], ss;
long long xm(long long x1, long long y1, long long x2, long long y2) {
	return x1 * y2 - x2 * y1;
}
int main() {
	scanf("%d", &n);
	s[ss++] = 0;
	for (int i = 1; i <= n + 1; i++) {
		if (i <= n) {
			scanf("%lf", &a[i]);
		}
		while (ss >= 2 && xm(s[ss - 1] - s[ss - 2], a[s[ss - 1]] - a[s[ss - 2]],
			i - s[ss - 2], a[i] - a[s[ss - 2]]) > 0) {
			ss--;
		}
		s[ss++] = i;
	}
	int t = 0;
	for (int i = 1; i <= n; i++) {
		while (i > s[t]) {
			t++;
		}
		ull res = (ull)a[s[t]] * (i - s[t - 1]) + (ull)a[s[t - 1]] * (s[t] - i);
		res *= 100000;
		res /= s[t] - s[t - 1];
		printf("%llu\n", res);
	}
	return 0;
}

题解