Cod sursa(job #2071727)

Utilizator gundorfMoldovan George gundorf Data 20 noiembrie 2017 22:23:35
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.83 kb
#include <iostream>
#include <fstream>
#define Nmax 1004
#define Mmax 2000000
#include <algorithm>
using namespace std;
ifstream fin("trapez.in");
ofstream fout("trapez.out");

int n,k;
struct element //punctele din spatiu citite
{
    int x,y;
}elemente[Nmax];
struct fractie //panta dreptelor, sub forma de fractie
{
    int numitor,numarator;
}a[Mmax];

void Citire () //citesc coordonatele si numarul lor
{
    int i;
    fin>>n;
    for (i = 1;i <= n ; i++ )
        fin>>elemente[i].x>>elemente[i].y;
}

int cmmdc (int x,int y)
{
    if ( y == 0 ) return x;
    else return cmmdc ( y , x % y );
}

int abs (int x)
{
    if ( x < 0 ) return (-1) * x;
    return x;
}

void Initializare_Fractie () //  creez vectorul fractie, adica creez toate dreptele posibile folosind coordonatele citite si salvez panta dreptei sub forma de fractie
{int i,j;

for (i = 1 ; i < n ; i++ )
    for (j = i + 1 ; j <= n ; j++ )
{
    int sus,jos,numitorcomun;

    sus = elemente[j].y - elemente[i].y;

    jos = elemente[j].x - elemente[i].x;

    numitorcomun = cmmdc(abs(sus),abs(jos)); //reduc fractie prin cel mai mare divizor comun

    k++;
    a[k].numarator=sus/numitorcomun;
    a[k].numitor=jos/numitorcomun;

}

}
void swap (fractie &x,fractie &y)
{
    fractie aux;
    aux=x;
    x=y;
    y=aux;
}
int Pivotare (int s,int d) // sortez structura fractie pe baza pantei, in sens crescator
{
    int i=s-1,j,randpiv,panta1;
    float pantapiv;
    const int inf=99999999;
    fractie pivot;

    randpiv = rand() % (d-s) + s;

    pivot = a[randpiv];

    if (pivot.numitor == 0) pantapiv = inf;
            else pantapiv = (float) pivot.numarator / (float)pivot.numitor ;

    swap(a[d],a[randpiv]);

    for (j=s;j<d;j++)
        { if (a[j].numitor==0) panta1=inf;
            else panta1= (float) a[j].numarator / (float) a[j].numitor;
            if (panta1<=pantapiv)
        {
            i++;
            swap(a[i],a[j]);
        }
        }
       i++;
       swap(a[i],a[d]);
       return i;
}
void QS (int s,int d)
{
    int p;
    if (s<d)
    {
        int p=Pivotare(s,d);
        QS(s,p-1);
        QS(p+1,d);
    }
}

int main()
{int i,suma=0,nr;

    Citire();

    Initializare_Fractie();

    QS(1,k);

    i=1;

    while (i<k)
    { nr=1;
        if (a[i].numarator==0) while (a[i+1].numarator==0&&i<k) {i++;nr++;}
       else  if (a[i].numitor==0) while (a[i+1].numitor==0&&i<k) {i++;nr++;}
             else
             {
                 while (abs(a[i].numarator)==abs(a[i+1].numarator)&&abs(a[i].numitor)==abs(a[i+1].numitor)&&i<k) {i++;nr++;}
             }

    if (nr>=2) suma=suma+(nr*(nr-1))/2;
        i++;
    }
   /*for (i=1;i<=k;i++)
       fout<<a[i].numarator<<" "<<a[i].numitor<<"\n";*/

       fout<<suma;

    return 0;
}