Cod sursa(job #443095)

Utilizator siminescuPaval Cristi Onisim siminescu Data 16 aprilie 2010 00:30:27
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include<stdio.h>
struct structura{long long x,y;};
structura p[1001],t;
double v[501501],aux;
long long n,poz=-1,nr,s,nroy;
void citire()
{
	freopen("trapez.in","r",stdin);
	int i;
	scanf("%lld",&n);
	for(i=1;i<=n;i++)
		scanf("%lld%lld",&p[i].x,&p[i].y);
}
void swap(double &a,double &b)
{
	aux=a;a=b;b=aux;
}
void panta()
{
	int i,j;
	for(i=1;i<n;i++)
		for(j=i+1;j<=n;j++)
		{
			t.y=p[j].y-p[i].y;
			t.x=p[j].x-p[i].x;
			if(t.x!=0)
			{
				poz++;
				v[poz]=(double)t.y/t.x;
			}
			else nroy++;
		}
}
void DownHeap( int from, int to )
{
    for( int son=2*from; son < to; from=son, son=2*from )
    {
        if( son < to-1 && v[son+1] > v[son] )
            ++son;
        if( v[from] >= v[son] )
            return;
        swap( v[from], v[son] );
    }
}
void HeapSort( int from, int to )
{
    int i;
    for( i=(to-from)/2; i >= 0; --i )
        DownHeap( i, to );
    while( to > from )
    {
        swap( v[from], v[to-1] );
        --to;
        DownHeap( from, to );
    }
}
int main()
{
	int i;
	citire();
	panta();
	HeapSort(0,poz+1);
	freopen("trapez.out","w",stdout);
	aux=v[1];nr=1;
	for(i=2;i<=poz;i++)
	{
		//printf("%df ",vect[i]);
		if(v[i]==aux)
			nr++;
		else
		{
			s=s+nr*(nr-1)/2;
			nr=1;
			aux=v[i];
		}
	}
	printf("%lld\n",s+nroy*(nroy-1)/2);
}