Cod sursa(job #1873007)

Utilizator doc2177Dorian Croitoru doc2177 Data 8 februarie 2017 18:51:41
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <bits/stdc++.h>

using namespace std;

long gcd(const long & a, const long & b) {
	if (a==0) return b;
	return gcd(b%a,a);
}

int main() {
	freopen("trapez.in","r",stdin);
	freopen("trapez.out","w",stdout);

	int N;
	long x[1001], y[1001];
	cin >> N;
	map< pair<long, long>, long > slope;
	for (int i=0; i!=N; ++i) cin >> x[i] >> y[i] ;
	
	for (int i=1; i!=N; i++) 
		for (int j=0; j!=i; ++j) {
			if (x[i]==x[j]) slope[make_pair(0, 1)]+=1;
			else if (y[i]==y[j]) slope[make_pair(1, 0)]+=1;
			else {
				long dx = x[i] - x[j], dy= y[i] - y[j];
				if (dx<0) dx=-dx; if (dy<0) dy=-dy; 
				long d = gcd(min(dx,dy), max(dx,dy));
				slope[ make_pair( (x[i]-x[j])/d, (y[i]-y[j])/d )] +=1;  
			}
		}
	long long ans=0;
	for (map<pair<long, long>, long>::iterator it= slope.begin(); it!=slope.end(); ++it) {
		long i = it->second; ans+= i*(i-1)/2 ; 
		}
	cout << ans << endl;

return 0;
}