#include <bits/stdc++.h>
using namespace std;
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
#define dbg(x) "[" #x " = " << (x) << "]"
template<typename T>
bool minimize(T& a, const T& b){
if(a > b) return a = b, true;
return false;
}
template<typename T>
bool maximize(T& a, const T& b){
if(a < b) return a = b, true;
return false;
}
using ll = long long;
using db = double;
using ull = unsigned long long;
using ld = long double;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vc = vector<char>;
using vb = vector<bool>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vvi = vector<vl>;
using vvl = vector<vl>;
struct point{
ll x, y;
point(ll _x = 0, ll _y = 0) : x(_x), y(_y) {}
point& operator += (const point& a){
x += a.x; y += a.y;
return *this;
}
point& operator -= (const point& a){
x -= a.x; y -= a.y;
return *this;
}
friend point operator + (point a, const point& b){
return a += b;
}
friend point operator - (point a, const point& b){
return a -= b;
}
friend ostream& operator << (ostream& out, const point& p){
return out << '(' << p.x << ',' << p.y << ')';
}
};
ll cross2(const point& a, const point& b){
return a.x * b.y - a.y * b.x;
}
ll cross3(const point& a, point b, point c){
return cross2(b -= a, c -= a);
}
ll dot2(const point& a, const point& b){
return a.x * b.x + a.y * b.y;
}
ll dot3(const point& a, point b, point c){
return dot2(b -= a, c -= a);
}
struct Fraction{
ll a, b;
Fraction(ll _a, ll _b){
assert(_b != 0);
// cout << _a << ' ' << _b << '\n';
ll d = __gcd(abs(_a), abs(_b));
_a /= d; _b /= d;
if(_a < 0) _a = -_a, _b = -_b;
a = _a; b = _b;
// cout << "final : " << a << ' ' << b << '\n';
}
void refine(){
ll d = __gcd(abs(a), abs(b));
a /= d; b /= d;
if(a < 0) a = -a, b = -b;
}
friend bool operator == (const Fraction& a, const Fraction& b){ return a.a == b.a && a.b == b.b; }
friend bool operator != (const Fraction& a, const Fraction& b){ return !(a == b); }
bool operator < (const Fraction& f) const {
int cnt = (f.b < 0) ^ (b < 0);
return (cnt ? a * f.b > f.a * b : a * f.b < f.a * b);
}
friend ostream& operator << (ostream& out, const Fraction& o){
return out << '{' << o.a << ',' << o.b << '}';
}
};
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
freopen("task.inp", "r", stdin);
freopen("task.out", "w", stdout);;
#endif //LOCAL
int N;
cin >> N;
vector<point> points(N);
vi c(N);
for(int i = 0; i < N; ++i){
cin >> points[i].x >> points[i].y >> c[i];
}
vector<Fraction> slopes;
for(int i = 0; i < N; ++i){
for(int j = i+1; j < N; ++j){
if(points[i].x == points[j].x || points[i].y == points[j].y) continue;
Fraction frac(points[j].y - points[i].y, points[j].x - points[i].x);
// cout << i << ' ' << j << " : " << frac.a << ' ' << frac.b << '\n';
slopes.eb(frac);
}
}
sort(all(slopes));
compact(slopes);
// for(int i = 0; i < sz(slopes); ++i){
// cout << "[" << slopes[i].a << ", " << slopes[i].b << "]\n";
// }
ll ans = 0;
{
vector<pair<int, ll>> ar;
for(int i = 0; i < N; ++i) ar.eb(points[i].x, c[i]);
sort(all(ar));
vector<pair<int, ll>> new_ar;
for(int i = 0; i < N; ++i){
if(new_ar.empty() || new_ar.back().ff != ar[i].ff){
new_ar.pb(ar[i]);
} else new_ar.back().ss += ar[i].ss;
}
swap(new_ar, ar);
ll pref = 0, min_pref = 0;
for(int i = 0; i < sz(ar); ++i){
pref += ar[i].ss;
maximize(ans, pref - min_pref);
minimize(min_pref, pref);
}
}
{
vector<pair<int, ll>> ar;
for(int i = 0; i < N; ++i) ar.eb(points[i].y, c[i]);
sort(all(ar));
vector<pair<int, ll>> new_ar;
for(int i = 0; i < N; ++i){
if(new_ar.empty() || new_ar.back().ff != ar[i].ff){
new_ar.pb(ar[i]);
} else new_ar.back().ss += ar[i].ss;
}
swap(new_ar, ar);
ll pref = 0, min_pref = 0;
for(int i = 0; i < sz(ar); ++i){
pref += ar[i].ss;
maximize(ans, pref - min_pref);
minimize(min_pref, pref);
}
}
// cout << dbg(ans) << '\n';
for(int _ = 0; _ < sz(slopes); ++_){
Fraction f = slopes[_];
// cout << '(' << f.a << ' ' << f.b << ')' << '\n';
if(f.a != 3 || f.b != -2){
continue;
}
swap(f.a, f.b);
f.b = -f.b;
f.refine();
// cout << dbg(f.a) << dbg(f.b) << '\n';
vector<pair<Fraction, ll>> ar;
for(int i = 0; i < N; ++i){
// cout << dbg(points[i]) << '\n';
// cout << points[i].y * f.b << ' ' << points[i].x * f.a << ' ' << f.b << '\n';
ar.eb(Fraction(points[i].y * f.b - points[i].x * f.a, f.b), c[i]);
// cout << ar.back().ff << '\n';
}
sort(all(ar));
vector<pair<Fraction, ll>> new_ar;
for(int i = 0; i < N; ++i){
if(new_ar.empty() || new_ar.back().ff != ar[i].ff){
new_ar.pb(ar[i]);
} else new_ar.back().ss += ar[i].ss;
}
swap(new_ar, ar);
ll pref = 0, min_pref = 0;
for(int i = 0; i < sz(ar); ++i){
// cout << ar[i].ff.a << ' ' << ar[i].ff.b << " -> " << ar[i].ss << '\n';
pref += ar[i].ss;
maximize(ans, pref - min_pref);
minimize(min_pref, pref);
}
// cout << '\n';
}
cout << ans << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |