#include "bits/stdc++.h" using namespace std; #define int long long #define rep(i,a,b) for (int i = (a); i < (b); ++i) #define rin(i,a,b) rep(i,a,b+1) #define fox(i, n) rep(i,0,n) #define pb push_back #define sz(x) (int)x.size() #define all(x) begin(x), end(x) using vi = vector<int>; using pii = pair<int, int>; using db = double; template<class T> bool ckmax(T &a, T b) { return a < b ? a = b, 1 : 0; } template<class T> bool ckmin(T &a, T b) { return a > b ? a = b, 1 : 0; } template <class T> int sgn(T x) { return (x > 0) - (x < 0); } template<class T> struct Point { typedef Point P; T x, y; explicit Point(T x=0, T y=0) : x(x), y(y) {} bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); } bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); } P operator+(P p) const { return P(x+p.x, y+p.y); } P operator-(P p) const { return P(x-p.x, y-p.y); } P operator*(T d) const { return P(x*d, y*d); } P operator/(T d) const { return P(x/d, y/d); } T dot(P p) const { return x*p.x + y*p.y; } T cross(P p) const { return x*p.y - y*p.x; } T cross(P a, P b) const { return (a-*this).cross(b-*this); } T dist2() const { return x*x + y*y; } double dist() const { return sqrt((double)dist2()); } // angle to x-axis in interval [-pi, pi] double angle() const { return atan2(y, x); } P unit() const { return *this/dist(); } // makes dist()=1 P perp() const { return P(-y, x); } // rotates +90 degrees P normal() const { return perp().unit(); } // returns point rotated 'a' radians ccw around the origin P rotate(double a) const { return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); } friend ostream& operator<<(ostream& os, P p) { return os << "(" << p.x << "," << p.y << ")"; } }; struct Tree { struct T { int ans, left, right, sum; }; inline static const T unit = {0, 0, 0, 0}; T mk(int x) { return {max(0ll, x), max(0ll, x), max(0ll, x), x}; } T f(T a, T b) { return { max({a.ans, b.ans, a.right + b.left}), max(a.left, a.sum + b.left), max(b.right, a.right + b.sum), a.sum + b.sum }; } // (any associative fn) vector<T> s; int n; Tree(int n = 0, T def = unit) : s(2*n, def), n(n) {} void update(int pos, T val) { for (s[pos += n] = val; pos /= 2;) s[pos] = f(s[pos * 2], s[pos * 2 + 1]); } T query(int b, int e) { // query [b, e) T ra = unit, rb = unit; for (b += n, e += n; b < e; b /= 2, e /= 2) { if (b % 2) ra = f(ra, s[b++]); if (e % 2) rb = f(s[--e], rb); } return f(ra, rb); } }; using P = Point<int>; void solve() { int n; cin >> n; vector<P> v(n); vector<int> wt(n); fox(i, n) { int x, y, w; cin >> x >> y >> w; v[i] = P(x, y); wt[i] = w; } vi ord(n); iota(all(ord), 0); sort(all(ord), [&](int i, int j) { return pair(v[i].y, v[i].x) < pair(v[j].y, v[j].x); }); vi pos(n); fox(i, n) { pos[ord[i]] = i; } Tree tree(n); fox(i, n) tree.update(pos[i], tree.mk(wt[i])); struct Angle { P dir; int i, j; }; vector<Angle> angles; fox(i, n) { rep(j, i+1, n) { P dir = v[j] - v[i]; if (dir.y < 0 || (dir.y == 0 && dir.x < 0)) { angles.pb({dir * -1, j, i}); // todo: test - what if these are swapped? } else angles.pb({dir, i, j}); } } auto cmp = [&](auto a, auto b) { auto c = a.dir.cross(b.dir); if (c > 0) return true; if (c < 0) return false; return pair(ord[a.j], ord[a.i]) < pair(ord[b.j], ord[b.i]); }; sort(all(angles), cmp); int ans = tree.query(0, n).ans; for (int ai = -1; auto [_, i, j] : angles) { ai++; assert(abs(pos[i] - pos[j]) == 1); swap(pos[i], pos[j]); tree.update(pos[i], tree.mk(wt[i])); tree.update(pos[j], tree.mk(wt[j])); if (ai == sz(angles)-1 || cmp(angles[ai+1], angles[ai])) ckmax(ans, tree.query(0, n).ans); } cout << ans << '\n'; } signed main() { cin.tie(0)->sync_with_stdio(0); // int t; cin >> t; // while (t--) solve(); return 0; }