Cod sursa(job #455876)

Utilizator SmarandaMaria Pandele Smaranda Data 14 mai 2010 13:41:14
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include<stdio.h>
#include<math.h>
#define eps 0.00000000000001
#define NMAX (1000*1000)/2+2
#define INF 2000000100.0
struct trapez
{
	long x,y;
};
trapez t[1011];
double p[NMAX];
long vertical (trapez a , trapez b)
{
	return (a.x==b.x);
}

double panta (trapez a , trapez b)
{
	if (vertical (a,b)==1)
		return INF;
	return ((double)b.y-a.y)/(b.x-a.x);
}

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

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

int main()
{
	long n,i,j,u=0,num=0,rez=0;
	
	freopen("trapez.in","r",stdin);
	freopen("trapez.out","w",stdout);
	
	scanf("%ld",&n);
	for (i=1;i<=n;i++)
		scanf("%ld%ld",&t[i].x,&t[i].y);
	for (i=1;i<=n;i++)
		for (j=i+1;j<=n;j++)
			p[++u]=panta(t[i],t[j]);	
	quick(1,u);
	num=0;
	p[u+1]=p[u]+3;
	for (i=1;i<=u;i++)
		if (fabs(p[i]-p[i+1])<eps)
			num++;
		else
		{
			rez=rez+(num*(num+1)/2);
			num=0;
		}
	printf("%ld\n",rez);
	return 0;
}