ADAKOHL - hpclearn, C++ (gcc)

ADAKOHL - hpclearn

#include <bits/stdc++.h>
#define fi first
#define se second
#define ITER(i,n) for(int i=0; i<n; ++i)
#define REP(i,a,b) for(int i=a; i<=b; ++i)
#define pb push_back
#define mp make_pair
#define sc(a) cin >> a
#define sc2(a,b) cin >> a >> b
#define sc3(a,b,c) cin >> a >> b >> c
#define sc4(a,b,c,d) cin >> a >> b >> c >> d
#define sc_arr(a,n) for(int i=0; i<n; ++i) cin >> a[i]
#define prln() cout << "\n"
#define pr(a) cout << a
#define pr2(a,b) cout << a << ' ' << b
#define pr3(a,b,c) cout << a << ' ' << b << ' ' << c
#define pr4(a,b,c,d) cout << a << ' ' << b << ' ' << c << ' ' << d

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<pair<int,int>> vpi;

/*
	Bit manipulation --> x-1, -x, __builtin_popcount, __builtin_ctz, __builtin_clz
	Math --> __gcd
	Character --> tolower(), toupper(), isalnum(), isalpha, isdigit, isspace, isblank, 
	String to number --> stoi(), stoll(), stof(), stod(), stold(), atoi(), atoll(), atof(), atod(), atold(), printf("%4d") for padding
	Number to string --> to_string()
	Double --> printf("%.3Lf"), typecast instead of floor, 1 + typecast instead of ceil
	String manipulation --> str.c_str(), string b(char*), auto pos = str.find(char), string::npos
*/

struct pair_hash
{
    template <class T1, class T2>
    std::size_t operator() (const std::pair<T1, T2> &pair) const {
        return std::hash<T1>()(pair.first) ^ std::hash<T2>()(pair.second);
    }
};

struct tuple_hash
{
    template <class T1, class T2, class T3>
    std::size_t operator() (const std::tuple<T1, T2, T3> &tup) const {
        return std::hash<T1>()(get<0>(tup)) ^ std::hash<T2>()(get<1>(tup)) ^ std::hash<T2>()(get<2>(tup));
    }
};

ll get_point_cnt(ll pair_cnt) {
	return (sqrt(0.25+2*pair_cnt)+0.5);
}

int main() {
	ios_base::sync_with_stdio();
	cin.tie(0);
	cout.tie(0);

unordered_map<ll, ll> pair_point_cnt;
	REP(i, 1, 3000) {
		pair_point_cnt[i*(i-1)/2] = i;
	}

int t; scanf("%d", &t);
	while (t--) {
		int n; scanf("%d", &n);
		tuple<ll, ll, ll> points[n];
		ll ans = 0;
		ITER(i, n) {
			ll x, y, q; scanf("%lld%lld%lld", &x, &y, &q);
			points[i] = {x, y, q};
			ans = max(ans, q);
		}
		unordered_map<tuple<ll, ll, ll>, ll, tuple_hash> line_sum;
		unordered_map<tuple<ll, ll, ll>, ll, tuple_hash> line_cnt;
		ITER(i, n) {
			REP(j, i+1, n-1) {
				ll x1 = get<0>(points[i]);
				ll x2 = get<0>(points[j]);
				ll y1 = get<1>(points[i]);
				ll y2 = get<1>(points[j]);
				ll a = x2-x1;
				ll b = y2-y1;
				ll c = x2*y1-y2*x1;
				ll g = __gcd(c, __gcd(a, b));
				a /= g; b /= g; c /= g;
				tuple<ll, ll, ll> line = make_tuple(a, b, c);
                if (line_sum.find(line) == line_sum.end()) {
                    line_sum[line] = 0; line_cnt[line] = 0;
                }
				line_sum[line] += (get<2>(points[i]) + get<2>(points[j]));
				line_cnt[line]++;
			}
		}
		for (auto it = line_sum.begin(); it != line_sum.end(); ++it) {
			tuple<ll, ll, ll> line = it -> fi;
			ll sum = it -> se;
			ll cnt = pair_point_cnt[line_cnt[line]];
			ans = max(ans, sum/(cnt-1));
//            pr("Harshal "); pr(cnt); pr(' '); pr(sum); prln();
		}
		printf("%lld\n", ans);
	}
	return 0;
}


run \| edit \| history \| help	-1