Cod sursa(job #315726)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 16 mai 2009 21:50:10
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include<stdio.h>
#include<math.h>
#define eps 0.0000000000001
struct point
{
	double x,y;
};
int n,nr,sol;
point v[1002];
double p[500003];

void read()
{
	freopen("trapez.in","r",stdin);
	freopen("trapez.out","w",stdout);
	scanf("%d",&n);
	int i;
	for(i=1;i<=n;i++)
	{
		scanf("%lf%lf",&v[i].x,&v[i].y);
	}
}

int part(int st, int dr)
{
	int i,j,m;
	double aux,piv;
	m=(st+dr)>>1;
	piv=p[m];
	i=st-1;
	j=dr+1;
	while(1)
	{
		do{++i;}while((piv-p[i])>=eps);
		do{--j;}while((p[j]-piv)>=eps);
		if(i<j)
		{
			aux=p[i];
			p[i]=p[j];
			p[j]=aux;
		}
		else
			return j;
	}
}

void quick(int st, int dr)
{
	int piv;
	if(st<dr)
	{
		piv=part(st,dr);
		quick(st,piv);
		quick(piv+1,dr);
	}
}

void rez()
{
	int i,j;
	for(i=1;i<n;i++)
		for(j=i+1;j<=n;j++)
		{
			if(v[i].x==v[j].x)
				p[++nr]=2000000002;
			else
				p[++nr]=(v[j].y-v[i].y)/(v[j].x-v[i].x);
		}
	quick(1,nr);
	int l=1;
	for(i=1;i<nr;i++)
		if(fabs(p[i]-p[i+1])<eps)
			l++;
		else
		{
			sol=sol+l*(l-1)/2;
			l=1;
		}
	printf("%d\n",sol);
}

int main()
{
	read();
	rez();
	return 0;
}