Cod sursa(job #2774173)

Utilizator racsosabeVictor Racso Galvan Oyola racsosabe Data 10 septembrie 2021 02:10:03
Problema Trapez Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.89 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, long long>> 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);
			int type = dx == 0 ? 2 : 1;
			long long num;
			long long den;
			if(type == 1){
				num = 1ll * y[i] * dx - 1ll * x[i] * dy;
				den = dx;
			}
			else{
				num = 1ll * x[i] * dy - 1ll * y[i] * dx;
				den = dy;
			}
			fix<long long>(num, den);
			slopes.emplace_back(make_pair(dx, dy));
			lines.emplace_back(make_tuple(dx, dy, type, num, den));
		}
	}
	sort(slopes.begin(), slopes.end());
	sort(lines.begin(), lines.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;
	cnt = 0;
	for(int i = 0; i < lines.size(); i++){
		if(i and lines[i - 1] != lines[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;
}