Cod sursa(job #865649)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 26 ianuarie 2013 19:27:10
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <fstream>
#include <algorithm>

using namespace std;
//mai mult
#define inf 2000000005

struct element
{
	long long int x;
	long long int y;
}pante[500005];

element panta(int x1,int y1, int x2, int y2)
{
	y2-=y1;
	x2-=x1;
	
	element a;
	
	a.y=y2;
	a.x=x2;
	
	if(x2==0)
	{
		a.y=inf;
		a.x=1;
	}
	
	if(y2==0)
	{
		if(x2<0)
			a.x=-x2;
	}
	
	return a;
}

bool operator<(const element &a,const element &b)
{
	element c,d;
	c.x=a.x;
	c.y=a.y;
	
	d.x=b.x;
	d.y=b.y;
	
	if(c.x<=0 && c.y<=0)
	{
		c.x=-c.x;
		c.y=-c.y;
	}
	
	if(d.x<=0 && d.y<=0)
	{
		d.x=-d.x;
		d.y=-d.y;
		
	}
	if((c.x>=0 && d.x<0) || (c.x<0 && d.x>=0))
		return ((c.y*d.x)>(c.x*d.y));
	else
	return ((c.y*d.x)<(c.x*d.y));
}

bool compara(const element &a,const element &b)
{
	return ((a.x*b.y)==(b.x*a.y));
}

int main()
{
	ifstream fin("trapez.in");
	ofstream fout("trapez.out");
	
	int n,i,j;
	long long int vx[500005];
	long long int vy[500005];
	int poz=0;
	fin>>n;
	for(i=0;i<n;i++)
	{
		fin>>vx[i];
		fin>>vy[i];
	}
	//fout<<'\n';
	for(i=0;i<n;i++)
		for(j=i+1;j<n;j++)
			if(vx[i]!=vx[j] || vy[i]!=vy[j])
			{
				pante[poz++]=panta(vx[i],vy[i],vx[j],vy[j]);
		//		fout<<pante[poz-1].x<<' '<<pante[poz-1].y<<endl;
			}
	//fout<<"da\n";
	//		fout<<'\n';
	long int trapeze=0;	
	sort(pante,pante+poz);
	long int bune=1;
//	fout<<pante[0].x<<' '<<pante[0].y<<'\n';
	for(i=1;i<poz;i++)
	{
		//fout<<pante[i].x<<' '<<pante[i].y<<'\n';
		
		if(compara(pante[i],pante[i-1])==1)
		{
			//fout<<i<<" = "<<i-1<<'\n';
			bune++;
		}
		else
		{
			trapeze+=(((bune)*(bune-1))/2);
			//fout<<"trapeze creste cu "<<(((bune)*(bune-1))/2)<<'\n';
			bune=1;
		}
	}
	
	trapeze+=(((bune)*(bune-1))/2);
	
	fout<<trapeze<<'\n';
	fin.close();
	fout.close();
	return 0;
}