Cod sursa(job #467593)

Utilizator crushackPopescu Silviu crushack Data 29 iunie 2010 16:38:32
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <stdio.h>
#define lung 1000

struct Point
{int x,y;} a[lung];
int N;

struct Fr
{long long nr,num;
} p[lung*lung];

void citire()
{
	int i;
	freopen("trapez.in","r",stdin);
	scanf("%d",&N);
	for (i=0;i<N;i++)
		scanf("%d%d",&a[i].x,&a[i].y);
	fclose(stdin);
}

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

void schimb(Fr &a,Fr &b)
{
	Fr tmp=a;
	a=b;
	b=tmp;
}

void qsort(int ls,int ld)
{
	int i,j;
	if (ls>=ld)
		return;
	i=ls;
	for (j=ls+1;j<=ld;j++)
		if (p[j].nr/(float)p[j].num<p[ls].nr/(float)p[ls].num)
		{
			i++;
			schimb(p[i],p[j]);
		}
	schimb(p[i],p[ls]);
	qsort(ls,i-1);
	qsort(i+1,ld);
}

int rez()
{
	int i,j,nr,Rez,c;
	long long x;
	nr=0;
	for (i=0;i<N;i++)
		for (j=i+1;j<N;j++)
		{
			p[nr].nr= a[j].y-(long long)a[i].y;
			p[nr].num=a[j].x-(long long)a[i].x;
			x= cmmdc(p[nr].nr,p[nr].num);
			p[nr].nr/=x, p[nr].num/=x;
			if (!p[nr].num) nr--;
			nr++;
		}
	qsort(0,nr-1);
	Rez=0;c=1;
	for (i=1;i<nr;i++)
	{
		if ( (p[i].num==p[i-1].num && p[i].nr==p[i-1].nr) || ( p[i].num==-p[i-1].num && p[i].nr==-p[i-1].nr  ))
			c++;
		else
		{
			Rez+= c*(c-1)/2;
			c=1;
		}
	}
	Rez+=c*(c-1)/2;
	return Rez;
}

void scriere(int x)
{
	freopen("trapez.out","w",stdout);
	printf("%d\n",x);
	fclose(stdout);
}

int main()
{
	citire();
	scriere(rez());
	return 0;
}