Seletiva IOI 2017

jogo.cpp

// Ivan Carvalho
// Jogo - Seletiva IOI - OBI 2017
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll NEG = -1e17;
struct point{
	ll x,y,v;
};
bool compara(point A,point B){
	if(A.x != B.x) return A.x < B.x;
	return A.y < B.y;
}
ll n,resposta;
vector<point> V;
int main(){
	cin.tie(0);ios_base::sync_with_stdio(0);
	cin >> n;
	resposta = NEG;
	for(int i = 0;i<n;i++){
		point p;
		cin >> p.x >> p.y >> p.v;
		V.push_back(p);
	}
	sort(V.begin(),V.end(),compara);
	for(int i = 0;i<n;i++){
		unordered_map<double,ll> mapa;
		ll special = 0;
		ll dentro = V[i].v;
		for(int j = i - 1;j>=0;j--){
			double dy = V[j].y - V[i].y;
			double dx = V[j].x - V[i].x;
			if(V[j].x == V[i].x){
				special += V[j].v;
				resposta = max(resposta, special + dentro );
				continue;
			}
			mapa[dy/dx] += V[j].v;
			resposta = max(resposta, mapa[dy/dx] + dentro );
		}
		mapa.clear();
		special = 0;
		for(int j = i + 1;j<n;j++){
			double dy = V[j].y - V[i].y;
			double dx = V[j].x - V[i].x;
			if(V[j].x == V[i].x){
				special += V[j].v;
				resposta = max(resposta, special + dentro );
				continue;
			}
			mapa[dy/dx] += V[j].v;
			resposta = max(resposta, mapa[dy/dx] + dentro );
		}
	}
	cout << resposta << endl;
	return 0;
}