Cod sursa(job #865660)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 26 ianuarie 2013 19:54:58
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.55 kb
//Din cate se pare, rezolvarea prin numere reale e de 5 ori mai rapida, dar ideea e aceeasi, in plus, e mult mai scurta ce cu numere reale
#include <fstream>
#include <algorithm>

using namespace std;

//Definim infinitul ca fiind mai mare decat orice panta obtinubila
#define inf 2000000005

//O panta are numarator (x) si numitor (y)
struct element
{
	long long int x;
	long long int y;
}pante[500005];

//Intoarce panta dreptei ce trece prin cele doua puncte descrise in parametrii
element panta(int x1,int y1, int x2, int y2)
{
	//Facem scaderea
	y2-=y1;
	x2-=x1;
	
	//Declaram o noua panta, pe care o vom intoarce in main cand va fi nevoie
	element a;
	
	//Initial primeste numerele calculate cu 2 randuri mai sus
	a.y=y2;
	a.x=x2;
	
	//Avem si cazuri particulare
	//Pentru x2=0, impartirea la 0 o evitam folosind 1 in loc de 0 pe x si infinit pe y (practic este cazul paralelelor cu ordonata)
	if(x2==0)
	{
		a.y=inf;
		a.x=1;
	}
	
	//Cazul paralelelor cu abscisa, unde nu conteaza daca intoarcem dreapta invers cu 180 de grade, caci va fi tot paralela
	if(y2==0)
		if(x2<0)
			a.x=-x2;
	
	//Dupa aceste eventuale modificari, redurnam raspunsul
	return a;
}

//Definim operatorul < pentru structura element
bool operator<(const element &a,const element &b)
{
	//Copiem pe a si b in c si d
	element c,d;
	c.x=a.x;
	c.y=a.y;
	
	d.x=b.x;
	d.y=b.y;
	
	//Daca putem, simplificam cele doua fractii prin -1
	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;
		
	}
	
	//Acum, daca numai unul dintre numaratori este negativ, pentru ca a doua fractie sa fie mai mare,
	//trebuie ca primul membru sa fie mai mare decat al doilea, nu mai mic
	if((c.x>=0 && d.x<0) || (c.x<0 && d.x>=0))
		return ((c.y*d.x)>(c.x*d.y));  //Formula determinate adapdand teorema fundamentala a proportiilor
	return ((c.y*d.x)<(c.x*d.y));
}

//Determina daca doua pante sunt egale
bool compara(const element &a,const element &b)
{
	return ((a.x*b.y)==(b.x*a.y)); //Prin teorema fundamentala a proportiilor, pentru a nu avea erori de calcul
}

int main()
{
	//Deschiderea fisierelor de intrare si iesire
	ifstream fin("trapez.in");
	ofstream fout("trapez.out");
	
	//Declaram doi vectori, unul pentru abscisele initiale si unul pentru ordonatele initiale
	long long int vx[500005];
	long long int vy[500005];
	
	//Numarul de puncte si doua variabile contor
	int n,i,j;
	
	//Numarul de segmente
	int poz=0;
	
	//Citim Segmentele
	fin>>n;
	
	for(i=0;i<n;i++)
	{
		fin>>vx[i];
		fin>>vy[i];
	}
	
	//Introducem segmentele cu lungime strict pozitiva in vectorul de pante
	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]);
			
	
	//Sortam crescator dupa panta dreptelor 
	sort(pante,pante+poz);
	
	//Numarul de trapeze
	long int trapeze=0;
	
	//Numarul de pante egale consecutive
	long int bune=1;
	
	for(i=1;i<poz;i++)
	{
		//Daca sunt egale, numarul de consecutive creste
		if(compara(pante[i],pante[i-1])==1)
			bune++;
		else
		{
			//Daca nu, numarul de trapeze creste
			trapeze+=(((bune)*(bune-1))/2);
			
			//Iar bune revine la 1, caci nu egal cu anteriorul
			bune=1;
		}
	}
	
	//La final, daca nu mai avem o panta diferita de cele anterioare, cele anterioare nu se vor mai adauga la rezultat,
	//deci, le adaugam noi
	trapeze+=(((bune)*(bune-1))/2);
	
	//Afisam raspunsul
	fout<<trapeze<<'\n';
	
	//Inchidem fisierele de intrare si iesire
	fin.close();
	fout.close();
	return 0;
}