有点厉害的题。也可能是我没见过这类套路。

$\mathcal{O}(n^4)$ 是简单的，枚举凸包底端的点，极角排序后跑 dp 即可。由于常数巨小可以随便过，但是我们不是这么随便的人，所以还是搓正解吧（

预处理三角形内点权和与 dp 转移都是 $\mathcal{O}(n^3)$ 的，需要进一步优化。

Part I：三角形内数点

假设我们考察的是 $i<j$ 与原点构成的三角形。对于一个点 $k$，他必须要满足 $i<k<j$ 才可能被计入贡献。

这看着怎么这么像一维限制，那是不是得想办法凑出第二维？三角形数点我不会，但是二维数点我会啊！

发现 $i<k<j$ 本质上是限制了夹角的范围。考虑用两个角就能夹出来一个三角形，于是我们将 $i+1\sim n$ 的点以 $i$ 为中心极角排序，得到每个点的排名 $rk$，那么 $k$ 能造成贡献的的条件为 $rk_k<rk_j$。这样就是二维数点了，上树状数组即可，时间复杂度 $\mathcal{O}(n^2\log n)$。实测只做这个优化也跑的飞快。

Part II：dp 转移

朴素的转移就是设 $dp_{i,j}$ 表示上一条边为 $i\to j$ 时的答案，转移需要枚举上一个点 $k$ 并判断是否能构成凸包，然后 $dp_{i,j}\gets dp_{k,i}+w(i,j)$。

也就是我们要做的是快速求 $\max_k dp_{k,i}$。注意到极角排序后 $k$ 构成一段前缀，前缀和优化 dp 即可。时间复杂度 $\mathcal{O}(n^2\log n)$。

于是我们在 $\mathcal{O}(n^3\log n)$ 的复杂度下解决了这个问题。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 3e2 + 10;

typedef struct Point {
	ll x, y;
	Point(ll x = 0, ll y = 0) : x(x), y(y) {}
	Point operator - (const Point &rhs) const { return Point(x - rhs.x, y - rhs.y); }
	ll operator ^ (const Point &rhs) const { return x * rhs.y - y * rhs.x; }
} Vector;

int n, m; pair<Point, ll> a[MAXN], b[MAXN];

ll w[MAXN][MAXN], dp[MAXN][MAXN], ans = -1e18;

int id[MAXN], rk[MAXN]; ll c[MAXN];

inline void add(int k, ll x) { for (int i = k; i <= m; i += i & -i) c[i] += x; }
inline ll ask(int k) { ll res = 0; for (int i = k; i; i &= i - 1) res += c[i]; return res; }

inline
void solve() {
	sort(b + 1, b + m + 1, [](auto x, auto y) -> bool {
		if (!x.first.x && !x.first.y) return 1;
		return (x.first ^ y.first) > 0;
	});
	for (int i = 2; i < m; i++) {
		for (int j = i + 1; j <= m; j++) id[j] = j;
		sort(id + i + 1, id + m + 1, [=](auto x, auto y) {
			return (b[x].first - b[i].first ^ b[y].first - b[i].first) < 0;
		});
		for (int j = i + 1; j <= m; j++) rk[id[j]] = j;
		for (int j = 1; j <= m; j++) c[j] = 0;
		for (int j = i + 1; j <= m; j++) w[i][j] = b[i].second + ask(rk[j]), add(rk[j], b[j].second);
	}
	memset(dp, 0xc0, sizeof dp);
	for (int i = 2; i <= m; i++) dp[1][i] = b[1].second;
	for (int i = 2; i < m; i++) {
		vector<int> tmp;
		for (int j = 1; j <= m; j++) if (j != i) tmp.emplace_back(j);
		sort(tmp.begin(), tmp.end(), [=](int x, int y) -> bool {
			Vector tx = x < i ? b[i].first - b[x].first : b[x].first - b[i].first;
			Vector ty = y < i ? b[i].first - b[y].first : b[y].first - b[i].first;
			return (tx ^ ty) > 0;
		});
		ll val = -1e18;
		for (int j : tmp) {
			if (j > i) dp[i][j] = max(dp[i][j], val + w[i][j]);
			else val = max(val, dp[j][i]);
		}
	}
	for (int i = 2; i <= m; i++) {
		for (int j = i + 1; j <= m; j++) ans = max(ans, dp[i][j] + b[j].second);
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%lld%lld%lld", &a[i].first.x, &a[i].first.y, &a[i].second);
	for (int i = 1; i <= n; i++) {
		m = 0;
		for (int j = 1; j <= n; j++) {
			if (a[j].first.y >= a[i].first.y) {
				b[++m] = make_pair(a[j].first - a[i].first, a[j].second);
			}
		}
		solve();
	}
	printf("%lld", ans);
}