Cod sursa(job #3143395)

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

int gcd(int a, int b)
{
	if(!b)
		return a;
	return gcd(b, a % b);
}

typedef unsigned long long ull;
int solve(vector<vector<int>> v)
{
	int n = v.size(), ans = 0;
	vector<ull> arr;
	ull base = 2000000005;
	
	int vert = 0;
	for(int i = 0;i < n;++i)
		for(int j = i + 1;j < n;++j)
		{
			int x = v[i][0] - v[j][0];
			int y = v[i][1] - v[j][1];
			if(!x)
				++vert;
			else
			{
				int gc = gcd(x, y);
				arr.push_back((ull) x / gc * base + y / gc);
			}
		}
	ans += (vert * (vert - 1)) / 2;
	sort(arr.begin(), arr.end());
	int cnt = 1;
	for(int i = 1;i < arr.size();++i)
	{
		if(arr[i] != arr[i - 1])
		{
			ans += (cnt * (cnt - 1)) / 2;
			cnt = 1;
		}
		else
			++cnt;
	}
	return ans + (cnt * (cnt - 1)) / 2;
}


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";
}