Cod sursa(job #3143391)

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

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

bool comp(const vector<int>& a, const vector<int>& b)
{
	if(a[0] != b[0])
		return a[0] < b[0];
	return a[1] < b[1];
}

int solve(vector<vector<int>> v)
{
	int n = v.size(), ans = 0;
	vector<vector<int>> arr;
	
	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({x / gc, y / gc});
			}
		}
	ans += (vert * (vert - 1)) / 2;
	sort(arr.begin(), arr.end(), comp);
	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";
}