Pagini recente » Cod sursa (job #3126479) | Cod sursa (job #1861189) | Cod sursa (job #2600166) | Rating Muresan Andrei (andmury) | Cod sursa (job #865660)
Cod sursa(job #865660)
//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;
}