Cod sursa(job #1873034)

Utilizator doc2177Dorian Croitoru doc2177 Data 8 februarie 2017 19:05:20
Problema Trapez Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <bits/stdc++.h>

typedef long long big;
using namespace std;

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

return 0;
}