Cod sursa(job #442204)

Utilizator siminescuPaval Cristi Onisim siminescu Data 13 aprilie 2010 23:06:21
Problema Trapez Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include<stdio.h>
struct structura{int x,y;};
structura p[1001],t;
float vect[501501],aux;
int n,poz,nr,s;
void citire()
{
	freopen("trapez.in","r",stdin);
	int i;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d%d",&p[i].x,&p[i].y);
}
void panta()
{
	int i,j;
	for(i=1;i<n;i++)
		for(j=i+1;j<=n;j++)
		{
			poz++;
			t.y=p[j].y-p[i].y;
			t.x=p[j].x-p[i].x;
			if(t.x!=0)
				vect[poz]=(float)t.y/t.x;
			else vect[poz]=1,1234567;
		}
}
void quickSort(int stanga, int dreapta)
{int i = stanga, j = dreapta;
float pivot = vect[(stanga + dreapta) / 2],tmp;
while (i <= j) {
	while (vect[i] < pivot)
		i++;
	while (vect[j] > pivot)
		j--;
	if (i <= j) {
		tmp = vect[i];
		vect[i] =vect[j];
		vect[j] = tmp;
		i++;
		j--;
	}
}
if (stanga < j)
	quickSort(stanga, j);
if (i < dreapta)
	quickSort(i, dreapta);
}  
int main()
{
	int i;
	citire();
	panta();
	quickSort(1,poz);
	freopen("trapez.out","w",stdout);
	aux=vect[1];nr=1;
	for(i=2;i<=poz;i++)
	{
		//printf("%f ",vect[i]);
		if(vect[i]==aux)
			nr++;
		else
		{
			s=s+nr*(nr-1)/2;
			nr=1;
			aux=vect[i];
		}
	}
	printf("%d\n",s);
}