Cod sursa(job #155803)

Utilizator nashnash mit nash Data 12 martie 2008 10:26:45
Problema Trapez Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.05 kb
// algoritmul este imcomplet... 
// se dau "n" puncte ....
// cate trapeze se pot forma cu ajutorul lor ...


#include <stdio.h>
#include <stdlib.h>
long long p[1001][2],n,nr,nr_t,i,j,sol,d[1001][2];
#define x 0
#define y 1

int produs(long long  a,long long  b,long long c,long long d) {

	long long x1 = p[a][x] - p[b][x];
	long long y1 = p[a][y] - p[b][y];
	long long x2 = p[c][x] - p[d][x];
	long long y2 = p[c][y] - p[d][y];

	return -(x1*y2 - y1*x2);
}

int cmp(const void *a,const void *b) {

	long long *a1 = (long long*)a;
	long long *b1 = (long long*)b;

	return produs(a1[0],a1[1],b1[0],b1[1]);
}

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

	scanf("%lld",&n);
	for(i=1;i<=n;i++)
		scanf("%lld %lld",&p[i][x],&p[i][y]);

	nr=-1;
	for(i=1;i<n;i++)
		for(j=i+1;j<=n;j++)
			d[++nr][0]=i,d[nr][1]=j;

	qsort(d,nr+1,sizeof(d[0]),cmp);
	
	nr_t=1;
	sol=0;
	for(i=1;i<=nr;i++) 
		if(produs(d[i][0],d[i][1],d[i-1][0],d[i-1][1])==0) 
			nr_t++;
		else {
			sol+=((nr_t-2)*(nr_t-1));
			nr_t=1;
		}
	printf("%lld",sol);
	return 0;
}