Cod sursa(job #214575)

Utilizator ilincaSorescu Ilinca ilinca Data 15 octombrie 2008 09:51:41
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <stdio.h>

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

struct point 
{
	int x, y;
};
struct fractie
{
	int numitor, numarator;
};

int n, nrp;
point p [nmax];
fractie 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);
}

int cmmdc (int a, int b)
{
	int r;
	while (b)
	{
		r=a%b;
		a=b;
		b=r;
	}
	return a;
}

void pante ()
{
	int i, j, a;
	for (i=1; i<=n; ++i)
		for (j=i+1; j<=n; ++j)
		{
			pnt [++nrp].numitor=p [i].x - p [j].x;
			pnt [nrp].numarator=p [i].y - p [j].y;
			a=cmmdc (pnt [nrp].numitor, pnt [nrp].numarator);
			pnt [nrp].numitor/=a;
			pnt [nrp].numarator/=a;
			if (pnt [nrp].numitor < 0)
			{
				pnt [nrp].numitor*=-1;
				pnt [nrp].numarator*=-1;
			}
		}
}

int partitie (int st, int dr)
{
	int i, j;
	fractie aux, piv;
	i=st-1;
	j=dr+1;
	piv=pnt [(st+dr)/2];
	while (1)
	{
		do {i++;} while ((pnt [i].numitor < piv.numitor) || (pnt [i].numitor == piv.numitor && pnt [i].numarator < piv.numarator));
		do {j--;} while ((pnt [j].numitor > piv.numitor) || (pnt [j].numitor == piv.numitor && pnt [j].numarator > piv.numarator));
		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;
	for (i=1; i<=nrp; i)
	{
		m=i;
		do 
		{
			++i;
		} while (pnt [i].numitor == pnt [i+1].numitor && pnt [i].numarator == pnt [i+1].numarator && i < nrp);
		m=i-m;
		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;
}