P12767 [POI 2018 R3] 围栏 Fence

翻译来自于 [LibreOJ](https://loj.ac/p/5075)。

**题目译自 [XXV Olimpiada Informatyczna — III etap](https://sio2.mimuw.edu.pl/c/oi25-3/dashboard/) [Ogrodzenie](https://szkopul.edu.pl/problemset/problem/guoc36QCEe4q47qruYB7HBV-/statement/)** 农夫 Bajtazar 刚购置了一块土地，上面生长着 $n$ 株植物。其中一些是果树，每年带来非负收益（果实价值不等）；另一些是杂草，只会造成损失（占用空间和阳光）。 Bajtazar 为每株植物估算了留下它的收益或损失。然而，拜托尼亚禁止破坏自然，他无法随意移除带来损失的植物。幸好，他需为土地建围栏，于是突发奇想：何必围住整块土地？只围住收益最大的部分即可！ Bajtazar 请你帮忙设计最优围栏。围栏需经济高效：他将选择部分植物，用弹性网固定于其上，围成的区域必须是面积大于 $0$ 的凸多边形。请帮助 Bajtazar 挑选支撑网的植物，最大化围栏内植物的收益总和。

第一行包含一个整数 $n$ $(n \geq 3)$，表示土地上植物数量。 接下来的 $n$ 行描述各植物，第 $i$ 行包含三个整数 $x_i, y_i, v_i$ $(-10^9 \leq x_i, y_i \leq 10^9, -10^9 \leq v_i \leq 10^9)$，分别表示第 $i$ 株植物在直角坐标系中的位置 $(x_i, y_i)$ 及其收益（若 $v_i$ 为负则为损失）。保证任意三株植物不在同一直线上。

输出一行，包含一个整数，表示围栏内植物可实现的最大收益总和。

**样例 1 解释** 图示展示了一种最大收益为 $3$ 的围栏设置。另一种同样最优的方案是固定网于点 $(0,0), (4,0), (4,4)$ 的植物。  **附加样例** 1. $n=8$，围住所有植物最优。 2. $n=100, x_i=i, y_i=i^2 \bmod 101, v_i=50-i$，植物排列形似甲虫。 3. $n=300$，植物构成凸多边形顶点，每隔一株收益 $1$，另一株损失 $1$。 详细子任务附加限制及分值如下表所示。 | 子任务 | 附加限制 | 分值 | | :---: | :--: | :---: | | $1$ | $n \leq 20$ | $30$ | | $2$ | $n \leq 100$ | $40$ | | $3$ | $n \leq 300$ | $30$ |