#include <bits/stdc++.h> #define ll long long #define sti string #define bit(n,i) ((n>>i) &1) #define itachi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define maxn 2005 #define fi first #define se second #define int long long using namespace std; const long double PI = acosl(-1.0L); const long double EPS = 1e-18L; int n; int X[maxn], Y[maxn], W[maxn]; struct Node { int sum, pre, suf, best; Node(int v = 0) { sum = v; pre = suf = best = max(0LL, v); } }; Node st[4 * maxn]; Node combine(const Node &L, const Node &R) { Node res; res.sum = L.sum + R.sum; res.pre = max(L.pre, L.sum + R.pre); res.suf = max(R.suf, R.sum + L.suf); res.best = max({L.best, R.best, L.suf + R.pre}); return res; } void build(int id, int l, int r, vector<int> &arr) { if (l == r) { st[id] = Node(arr[l]); return; } int mid = (l + r) >> 1; build(id<<1, l, mid, arr); build(id<<1|1, mid+1, r, arr); st[id] = combine(st[id<<1], st[id<<1|1]); } void update(int id, int l, int r, int pos, int val) { if (l == r) { st[id] = Node(val); return; } int mid = (l + r) >> 1; if (pos <= mid) update(id<<1, l, mid, pos, val); else update(id<<1|1, mid+1, r, pos, val); st[id] = combine(st[id<<1], st[id<<1|1]); } struct Event { long double ang; int u, v; bool operator < (const Event &other) const { if (fabsl(ang - other.ang) > EPS) return ang < other.ang; if (u != other.u) return u < other.u; return v < other.v; } }; signed main() { itachi cin>>n; for(int i=1;i<=n;i++){ cin>>X[i]>>Y[i]>>W[i]; } vector<Event> events; for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ long double dx=X[j]-X[i]; long double dy=Y[j]-Y[i]; long double ang=atan2l(-dx,dy); if(ang<0) ang+=PI; events.push_back({ang,i,j}); } } sort(events.begin(),events.end()); vector<int> ord(n+1); for(int i=1;i<=n;i++) ord[i]=i; sort(ord.begin()+1, ord.end(), [&](int a, int b) { if (X[a] != X[b]) return X[a] < X[b]; return Y[a] < Y[b]; }); vector<int> pos(n+1); for (int i = 1; i <= n; i++) pos[ord[i]] = i; /// build segment tree vector<int> arr(n+1); for (int i = 1; i <= n; i++) arr[i] = W[ord[i]]; build(1, 1, n, arr); int ans = st[1].best; for (int i = 0; i < (int)events.size();) { int j = i; while (j < (int)events.size() && fabsl(events[j].ang - events[i].ang) <= EPS) j++; for (int k = i; k < j; k++) { int u = events[k].u; int v = events[k].v; int pu = pos[u]; int pv = pos[v]; if (pu == pv) continue; swap(ord[pu], ord[pv]); pos[u] = pv; pos[v] = pu; update(1, 1, n, pu, W[ord[pu]]); update(1, 1, n, pv, W[ord[pv]]); } ans = max(ans, st[1].best); i = j; } cout << ans << "\n"; return 0; }