Cod sursa(job #2774172)

Utilizator racsosabeVictor Racso Galvan Oyola racsosabe Data 10 septembrie 2021 02:04:54
Problema Trapez Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 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;
	map<pair<int, int>, int> frec_slope;
	map<tuple<int, int, int, long long, long long>, int> frec_line;
	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);
			ans += frec_slope.count(make_pair(dx, dy)) ? frec_slope[make_pair(dx, dy)] : 0;
			ans -= frec_line.count(make_tuple(dx, dy, type, num, den)) ? frec_line[make_tuple(dx, dy, type, num, den)] : 0;
			frec_slope[make_pair(dx, dy)]++;
			frec_line[make_tuple(dx, dy, type, num, den)]++;
		}
	}
	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;
}