Cod sursa(job #1873395)

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

using namespace std;

typedef pair<long, long> pt;

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

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

	long N, a, b, k=0;
	cin >> N;
	pt p[N+1], slope[(N+1)*(N+1)];
	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 long xi = p[i].first, yi = p[i].second;
		for (int j=0; j!=i; ++j) {
			const long xj= p[j].first, yj=p[j].second;
			if (xi==xj) slope[k++] =  pt(0,1);
			else if (yi==yj) slope[k++] = pt(1,0); 
			else {
				long dx = xi-xj, dy= yi-yj;
				if (dy<0) dy=-dy; 
				long d = dx>dy ? gcd(dy,dx) : gcd(dx,dy); 
				slope[k++] = pt( dx/d, (yi-yj)/d );
				}
  			}
		}
	
	long long ans=0, nr=1;
	sort(slope, slope+k);
	for (int i=1; i!=k; ++i) { 
		if (slope[i]==slope[i-1]) nr++;
		else { ans += nr*(nr-1)/2 ; nr=1; }
	}
	cout << ans << endl;

return 0;
}