Cod sursa(job #443094)

Utilizator siminescuPaval Cristi Onisim siminescu Data 16 aprilie 2010 00:15:42
Problema Trapez Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include<fstream>
using namespace std;
struct structura{int x,y;};
structura p[1001],v[500001],t,aux;
int n,poz,cm,nroy,nrox,s,nr;
int absolut(int a)
{
	if(a<0)
		a=-a;
	return a;
}
int cmmdc(int a,int b)
{
	while(a!=b)
	{
		if(absolut(a)>absolut(b)){a=a%b;if(a==0)a=b;}
		else{b=b%a;if(b==0)b=a;}
	}
	return a;
}
void swap(structura a,structura b)
{
	aux=a;a=b;b=aux;
}
void citire()
{
	int i;
	ifstream f("trapez.in");
	f>>n;
	for(i=1;i<=n;i++)
		f>>p[i].x>>p[i].y;
}
void panta()
{
	int i,j;
	for(i=1;i<=n;i++)
		for(j=i+1;j<=n;j++)
		{
			t.x=p[j].x-p[i].x;t.y=p[j].y-p[i].y;
			if(t.x!=0&&t.y!=0)
			{
				cm=cmmdc(t.y,t.x);
				poz++;
				v[poz].x=t.x/cm;v[poz].y=t.y/cm;
			}
			else if(t.y==0)nroy++;
			else nrox++;
		}
}
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].y > v[son].y ||(v[son].y==v[son+1].y&&v[son+1].x>v[son].x))
            ++son;
        if( v[from].y > v[son].y||(v[from].y==v[son].y&&v[from].x>=v[son].x) )
            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,j;
	citire();
	panta();
	for(i=1;i<poz;i++)
		for(j=i+1;j<=poz;j++)
			if(v[j].y<v[i].y||(v[i].y==v[j].y&&v[j].x<v[i].x))
			{
				aux=v[i];v[i]=v[j];v[j]=aux;
			}
	aux=v[1];nr=1;s+=nroy*(nroy-1)/2;s+=nrox*(nrox-1)/2;
	for(i=2;i<=poz;i++)
	{
		if(aux.x==v[i].x&&aux.y==v[i].y)
			nr++;
		else
		{
			aux=v[i];
			s+=nr*(nr-1)/2;nr=1;
		}
	}
	ofstream g("trapez.out");
	g<<s<<'\n';
}