Cod sursa(job #155765)

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


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

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

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

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

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

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

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

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

	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d %d",&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*(nr_t-1));
			nr_t=1;
		}
	printf("%d",sol);
	return 0;
}