Участник:Andriygav/ADAKOHL

Материал из DISCOPAL
Перейти к: навигация, поиск
  • компилятор: gcc 8.3
#include <vector>
#include <algorithm>
#include <array>
#include <iostream>
using namespace std;
 
int greatest_common_divisor(int x, int y){
  return y ? greatest_common_divisor(y, x % y) : x;
}
 
int main(){
    int t;
    cin >> t;
 
    while(t--){
        int n;
        cin >> n;
        vector<int> x(n);
        vector<int> y(n);
        vector<int> q(n);
 
        for (int i = 0; i < n; ++i) {
        	cin >> x[i] >> y[i] >> q[i];
        }
 
        vector<array<int, 3>> v(n - 1);
 
        int ret = max(0, *max_element(q.begin(), q.end()));
        for(int i = 0; i < n; i++){
        	int m = 0;
        	for(int j = 0; j < n; ++j) if (i != j) {
        		int dx = x[j] - x[i];
        		int dy = y[j] - y[i];
        		if(dx < 0 || (dx == 0 && dy < 0)){
        			dx = -dx;
        			dy = -dy;
        		}
        		int g = greatest_common_divisor(abs(dx), abs(dy));
        		v[m++] = {{dx / g, dy / g, q[j]}};
        	}
 
        	sort(v.begin(), v.end());
        	int k = 0;
        	for(int j = 0; j < m; j = k){
            	int suma = 0;
            	for(k = j; k < m && v[j][0] == v[k][0] && v[j][1] == v[k][1]; k++){
            		suma += v[k][2];
            	}
            	ret = max(ret, suma + q[i]);
        	}
        }
        cout << ret << endl;
    }
    return 0;
}