Cod sursa(job #443093)

Utilizator siminescuPaval Cristi Onisim siminescu Data 16 aprilie 2010 00:08:28
Problema Trapez Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 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 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++;
		}
}
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';
}