Cod sursa(job #504525)

Utilizator AndreyPAndrei Poenaru AndreyP Data 27 noiembrie 2010 23:06:02
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 1010
#define fs first
#define sc second
#define mp make_pair
#define pii pair< int,int >
#define ll long long

int n;
pii p[N];
pii val[N*N];
int ind[N*N];
int dim=-1;
ll rez;

inline void citire() {
	scanf("%d",&n);
	for(int i=1; i<=n; ++i)
		scanf("%d%d",&p[i].fs,&p[i].sc);
}

inline int cmmdc(int a,int b) {
	int r;
	while(b!=0) {
		r = a%b;
		a = b;
		b = r;
	}

	return a;
}

inline int sgn(const int &x) {
	if(x<0)
		return -1;
	if(x>0)
		return 1;
	return 0;
}

bool compar(const int &x,const int &y) {
	return (val[x]<val[y]);
}

inline int modul(const int &x) {
	return ( (x<0) ? (-x) : (x) );
}

inline void rezolva() {
	int y,x;
	for(int i=1; i<n; ++i) {
		for(int j=i+1; j<=n; ++j) {
			y = p[i].sc-p[j].sc;
			x = p[i].fs-p[j].fs;

			int aux = cmmdc(modul(y),modul(x));
			x /= aux;
			y /= aux;

			switch(sgn(x)*sgn(y)) {
				case 0: {
						if(x==0)
							y = 1;
						else
							x = 1;
					}
				default: {
						 if(x<0) {
							 x = -x;
							 y = -y;
						 }
					 }
			}
                        ++dim;
			ind[dim] = dim;
			val[dim].fs = y;
			val[dim].sc = x;
			printf("(%d,%d) (%d,%d) --> %d %d\n",p[i].fs,p[i].sc,p[j].fs,p[j].sc,y,x);
		}
	}

	sort(ind,ind+dim+1,compar);

	int nr = 1;
	for(int i=1; i<=dim; ++i) {
		if(val[ind[i-1]]==val[ind[i]]) {
			++nr;
			continue;
		}

		rez += (((ll)nr*((ll)nr-1LL))>>1);
		nr = 1;
	}

        rez += (((ll)nr*((ll)nr-1LL))>>1);               	
}	

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

	citire();
	rezolva();

	printf("%lld\n",rez);

	return 0;
}