#include "bits/stdc++.h" #include <ranges> #ifdef LOCAL #include "dbg.h" #else #define dbg(...) ((__VA_ARGS__)) #endif #define int ll #define fox(i, n) for (int i = 0; i < (n); ++i) #define rep(i, a, b) for (int i = (a); i < (b); ++i) #define rin(i, a, b) for (int i = (a); i <= (b); ++i) #define rrep(i, a, b) for (int i = (a); i >= (b); --i) #define pb push_back #define eb emplace_back #define F first #define S second #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) #define setprec(x) cout << fixed << setprecision(x) using namespace std; template<class T> using V = vector<T>; using ll = long long; using vi = V<int>; using vll = V<ll>; using pii = pair<int, int>; using pll = pair<ll, ll>; using vpii = V<pii>; using vpll = V<pll>; template<class T> using pq = priority_queue<T>; template<class T> using pqg = priority_queue<T, V<T>, greater<>>; using i128 = __int128; istream& operator>>(istream &is, i128 &x) { ll y; is >> y; x = y; return is; } // modified from https://codeforces.com/blog/entry/75044?#comment-1106835 ostream &operator<<(ostream &os, i128 x) { if (x == 0) return os << '0'; if (x < 0) os << '-', x = -x; string s; while (x) s += char(x%10) + '0', x /= 10; reverse(all(s)); return os << s; } template<class T> int sz(T& container) { return (int) container.size(); } template<class T> void sort_unique(vector<T> &v) { sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); } template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; } template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int urand(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); } template<class T> void re(T& x) { cin >> x; } template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); } template<class A, class B> void re(pair<A, B>& p) { re(p.first, p.second); } template<class A> void re(vector<A>& x) { for(auto& i: x) re(i); } template<class A> void re1(vector<A>& x) { rep(i, 1, sz(x)) re(x[i]); } #define nl cout << '\n'; template<class T> void pr(T&& x) { cout << x << ' '; } template<class H, class... T> void pr(H&& h, T&&... t) { pr(h); pr(t...); } template<class A, class B> void pr(pair<A, B>&& p) { pr(p.first, p.second); } template<class A> void prnvec(const vector<A>& x) { for(auto& i: x) pr(i); nl; } template<class A> void prn1(const vector<A>& x) { rep(i, 1, sz(x)) pr(x[i]); nl; } template<class H, class... T> void prn(H&& h) { cout << h; nl; } template<class H, class... T> void prn(H&& h, T&&... t) { pr(h); prn(t...); } int bit_width(int x) { return bit_width(uint64_t(x)); } int bit_ceil(int x) { return bit_ceil(uint64_t(x)); } int popcount(int x) { return popcount(uint64_t(x)); } // note: i am using #define int long long /** * Author: Ulf Lundstrom * Date: 2009-02-26 * License: CC0 * Source: My head with inspiration from tinyKACTL * Description: Class to handle points in the plane. * T can be e.g. double or long long. (Avoid int.) * Status: Works fine, used a lot */ 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 Node { int ans; int left, right, sum; }; Node mk(int x) { return {max(0ll, x), x, x, x}; } struct Tree { typedef Node T; T unit = mk(0); 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, b.sum + a.right), a.sum + b.sum}; } // (any associative fn) vector<T> s; int n; Tree(int n = 0, T def = mk(0)) : 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<ll>; void solve() { int n; re(n); vector<pair<P, int>> v(n); for (auto &[pt, val] : v) { auto &[x, y] = pt; re(x, y, val); } sort(all(v), [&](auto a, auto b) { return pair(a.F.x, -a.F.y) < pair(b.F.x, -b.F.y); }); vi pos(n); iota(all(pos), 0); Tree tree(n); fox(i, n) { tree.update(i, mk(v[i].S)); } int ans = tree.query(0, n).ans; dbg(ans, pos, v); auto half = [](P p) { assert(p.x || p.y); return p.y < 0 || (p.y == 0 && p.x < 0); }; auto cmp = [&](P a, P b) { return pair(half(a), a.y * b.x) < pair(half(b), a.x * b.y); }; auto eq = [&](P a, P b) { return !cmp(a, b) && !cmp(b, a); }; struct M { P p; int i, j; }; vector<M> swaps; fox(i, n) { fox(j, i) { auto p = (v[j].F - v[i].F).perp(); if (half(p)) swaps.eb(p * -1, j, i); else swaps.eb(p, i, j); } } sort(all(swaps), [&](auto &a, auto &b) { return cmp(a.p, b.p) || (eq(a.p, b.p) && pair(a.p.cross(v[a.i].F), a.p.cross(v[a.j].F)) > pair(a.p.cross(v[b.i].F), a.p.cross(v[b.j].F))); }); fox(i, sz(swaps)) { auto &info = swaps[i]; swap(pos[info.i], pos[info.j]); assert(abs(pos[info.i] - pos[info.j]) == 1); tree.update(pos[info.i], mk(v[info.i].S)); tree.update(pos[info.j], mk(v[info.j].S)); if (i == sz(swaps) - 1 || !eq(swaps[i].p, swaps[i+1].p)) { ckmax(ans, tree.query(0, n).ans); dbg(tree.query(0, n).ans, info.p, pos); } } prn(ans); } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); #ifdef LOCAL cin.exceptions(cin.failbit); #endif // int t; // cin >> t; // rin(i, 1, t) solve(); return 0; }