Cod sursa(job #1873358)

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

using namespace std;

typedef long long big;
typedef pair<long long, long long> pt;

big gcd(big a, big b) {
	while (a) {
		b%= a ;
		swap(a,b);
	}
	return b;
}

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

	big N, a, b;
	pt p[1001];
	cin >> N;
	map< pt, big> slope;
	for (int i=0; i!=N; ++i) { cin >> a >> b ; p[i].first = a ; p[i].second=b; } 
	sort(p,p+N);
	
	for (int i=1; i!=N; i++) {
		const big xi = p[i].first, yi = p[i].second;
		for (int j=0; j!=i; ++j) {
			const big xj= p[j].first, yj=p[j].second;
			if (xi==xj) slope[make_pair(0, 1)]+=1;
			else if (yi==yj) slope[make_pair(1, 0)]+=1;
			else {
				big dx = xi - xj, dy= yi-yj;
				if (dy<0) dy=-dy; 
				big d = dx>dy ? gcd(dy,dx) : gcd(dx,dy); 
				slope[ make_pair( dx/d, (yi-yj)/d )] +=1;
				}
  			}
		}
	big ans=0;
	for (map< pt, big>::iterator it= slope.begin(); it!=slope.end(); ++it) {
		const big i = it->second; ans+= i*(i-1)/2 ; 
		}
	cout << ans << endl;

return 0;
}