Cod sursa(job #214574)

Utilizator ilincaSorescu Ilinca ilinca Data 15 octombrie 2008 09:29:30
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <stdio.h>

#define eps 0.0001
#define nmax 1005
#define inf 100
#define pr(x) fprintf(stderr,"%d ",x)

struct point 
{
	int x, y;
};

int n, nrp;
point p [nmax];
float pnt [nmax*nmax];

void scan ()
{
	int i;
	scanf ("%d", &n);
	for (i=1; i<=n; ++i)
		scanf ("%d%d", &p [i].x, &p [i].y);
}

void pante ()
{
	int i, j;
	for (i=1; i<=n; ++i)
		for (j=i+1; j<=n; ++j)
		{
			if (p [i].x - p [j].x)
				pnt [++nrp]=(float)(p [i].y-p [j].y)/(p [i].x-p [j].x);
			else
				pnt [++nrp]=inf;
		}
}

int partitie (int st, int dr)
{
	int i, j;
	float aux, piv;
	i=st-1;
	j=dr+1;
	piv=pnt [(st+dr)/2];
	while (1)
	{
		do {i++;} while (pnt [i] < piv);
		do {j--;} while (pnt [j] > piv);
		if (i < j)
		{
			aux=pnt [i];
			pnt [i]=pnt [j];
			pnt [j]=aux;
		}
		else
			return j;
	}
}

void quicks (int st, int dr)
{
	if (st < dr)
	{
		int p=partitie (st, dr);
		quicks (st, p);
		quicks (p+1, dr);
	}
}

int trapez ()
{
	int i, m, s=0;
	float a;
	for (i=1; i<=nrp; i)
	{
		m=i;
		do 
		{
			++i;
			a=pnt [i] - pnt [i+1];
			if (a < 0)
				a=-a;
		} while (a < eps && i < nrp);
		m=i-m;
		pr (i);
		if (m > 1)
			s+=(m-1)*m/2;
	}
	return s;
}

int main ()
{
	freopen ("trapez.in", "r", stdin);
	freopen ("trapez.out", "w", stdout);
	scan ();
	pante ();
	quicks (1, nrp);
	printf ("%d", trapez ());
	return 0;
}