Cod sursa(job #3143406)

Utilizator bent_larsenSturzu Antonio-Gabriel bent_larsen Data 29 iulie 2023 17:35:55
Problema Trapez Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
int gcd(int a, int b)
{
	if(!b)
		return a;
	return gcd(b, a % b);
}

int solve(vector<vector<int>> v)
{
	int n = v.size(), ans = 0;
	unordered_map<ull, int> mp;
	ull add = 2000000000;
	ull base = 4000000005ULL;
	
	int vert = 0;
	for(int i = 0;i < n;++i)
		for(int j = i + 1;j < n;++j)
		{
			int x = v[j][0] - v[i][0];
			int y = v[j][1] - v[i][1];
			if(!x)
				++vert;
			else
			{
				if(x < 0)
					x = -x, y = -y;
				int gc;
				if(y >= 0)
					gc = gcd(x, y);
				else
					gc = gcd(x, -y);
				++mp[(ull) x / gc * base + y / gc + add];
			}
		}
	ans += (vert * (vert - 1)) / 2;
	for(auto it: mp)
		ans += (it.second * (it.second - 1)) / 2;
	return ans;
}

int main() {
	freopen("trapez.in", "r", stdin);
	freopen("trapez.out", "w", stdout);
	int n;
	cin >> n;
	vector<vector<int>> v;
	for(int i = 0;i < n;++i)
	{
		vector<int> tmp(2);
		cin >> tmp[0] >> tmp[1];
		v.push_back(tmp);
	}
	cout << solve(v) << "\n";
}