Cod sursa(job #2774174)

Utilizator racsosabeVictor Racso Galvan Oyola racsosabe Data 10 septembrie 2021 02:25:24
Problema Trapez Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include<bits/stdc++.h>
using namespace::std;

void setIO(string name, bool input = true, bool output = true){
	string inputname = name + ".in";
	string outputname = name + ".out";
	if(input) freopen(inputname.c_str(), "r", stdin);
	if(output) freopen(outputname.c_str(), "w", stdout);
}

const int N = 1000 + 5;

int n;
int x[N];
int y[N];

template<class T>
void fix(T &a, T &b){
	if(a == 0) b = 1;
	if(b == 0) a = 1;
	T mcd = __gcd(abs(a), abs(b));
	a /= mcd;
	b /= mcd;
	if(a < 0){
		a = -a;
		b = -b;
	}
}

long long get_trapezoids(){
	long long ans = 0;
	vector<pair<int, int>> slopes;
	vector<tuple<int, int, int, long long, int>> lines;
	for(int i = 0; i < n; i++){
		for(int j = i + 1; j < n; j++){
			int dx = x[i] - x[j];
			int dy = y[i] - y[j];
			if(!dx and !dy) continue;
			fix<int>(dx, dy);
			slopes.emplace_back(make_pair(dx, dy));
		}
	}
	sort(slopes.begin(), slopes.end());
	int cnt = 0;
	for(int i = 0; i < slopes.size(); i++){
		if(i and slopes[i - 1] != slopes[i]){
			ans += 1ll * cnt * (cnt - 1) / 2;
			cnt = 1;
		}
		else cnt++;
	}
	ans += 1ll * cnt * (cnt - 1) / 2;
	return ans;
}

int main(){
	setIO("trapez");
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> x[i] >> y[i];
	}
	cout << get_trapezoids() << endl;
	return 0;
}