Cod sursa(job #434200)

Utilizator ironhideAfterBurner ironhide Data 5 aprilie 2010 12:32:26
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <stdio.h>
#define GNT 2000000002

long N,M,x[1002],y[1002],i,j,Sol;
double m[500002];

void QuickSort(long L,long R)
{
	long i,j,aux,piv;
	i=L;
	j=R;
	piv=m[(L+R)/2];
	while(i<=j)
	{
		while(m[i]<piv) i++;
		while(m[j]>piv) j--;
		if(i<=j)
		{
			aux=m[i];
			m[i]=m[j];
			m[j]=aux;
			i++;
			j--;
		}
	}
	if(L<j) QuickSort(L,j);
	if(i<R) QuickSort(i,R);
}

int main()
{
	freopen("trapez.in","r",stdin);
	scanf("%ld",&N);
	for(i=1;i<=N;i++) scanf("%ld%ld",&x[i],&y[i]);
	M=0;
	for(i=1;i<N;i++)
		for(j=i+1;j<=N;j++)
			if(x[j]!=x[i]) m[++M]=((y[j]-y[i])*1.0)/((x[j]-x[i])*1.0);
			else m[++M]=GNT;
	QuickSort(1,M);
	i=1;
	Sol=0;
	while(i<=M)
	{
		j=i;
		while(m[i]==m[j]) j++;
		j--;
		Sol+=((j-i)*(j-i-1))/2;
		i=j;
		i++;
	}
	freopen("trapez.out","w",stdout);
	printf("%ld\n",Sol);
	return 0;
}