Cod sursa(job #2216422)

Utilizator skoda888Alexandru Robert skoda888 Data 26 iunie 2018 18:05:36
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.67 kb

//Problema 47 - Trapez

#include <iostream>
#include <fstream>
#include <vector>
#include <float.h>

const long double INFINIT = LDBL_MAX;

struct Punct{
    long long x;
    long long y;
};

struct Panta{
    long long x1;
    long long y1;

    long long x2;
    long long y2;

    long double valoare;
};

void quicksort(std::vector<Panta>& p, int inf, int sup)
{
    int i = inf;
    int j = sup;
    long double pivot = p[(inf + sup) / 2].valoare;

    do{
        while(p[i].valoare < pivot && i < sup) ++i;
        while(p[j].valoare > pivot && j > inf) --j;

        if(i <= j){
            Panta temp = p[i];
            p[i] = p[j];
            p[j] = temp;
            ++i;
            --j;
        }
    }while(i <= j);

    if(i < sup) quicksort(p, i, sup);
    if(j > inf) quicksort(p, inf, j);
}

int main()
{
    std::ifstream in("trapez.in");
    std::ofstream out("trapez.out");

    int N;
    in >> N;

    Punct puncte[N + 1];
    int index = 1;
    while(in >> puncte[index].x >> puncte[index].y){
        ++index;
    }

    std::vector<Panta> pante;
    for(int i = 1; i < N; ++i){
        for(int j = i + 1; j <= N; ++j){
            Panta panta_noua;
            panta_noua.x1 = puncte[i].x;
            panta_noua.y1 = puncte[i].y;
            panta_noua.x2 = puncte[j].x;
            panta_noua.y2 = puncte[j].y;
            //calculez panta
            //panta = (y2 - y1) / (x2 - x1)
            if(panta_noua.x1 != panta_noua.x2){  //daca x2 - x1 != 0
                //atunci pot calcula panta utilizand formula obisnuita
                panta_noua.valoare = (float)(panta_noua.y1 - panta_noua.y2) / (panta_noua.x1 - panta_noua.x2);
            }
            else{
                //daca x2 - x1 = 0, atunci panta este teoretic egala cu infinit
                panta_noua.valoare = INFINIT;
            }
            pante.push_back(panta_noua);
        }
    }
    //sortez pantele in functe de valoarea acestora
    quicksort(pante, 0, pante.size() - 1);
    // for(int i = 0; i < pante.size(); ++i){
     //   std::cout << "( " << pante[i].x1 << " " << pante[i].y1 << " ), "<< "("<< pante[i].x2 << ", " << pante[i].y2 << " )" <<  pante[i].valoare << "\n";
    //}
    //determin toate pantele egale intre ele si le numar
    int num_trapeze = 0;
    for(int i = 0; i < pante.size() - 1; ++i){
        bool ok = true;
        for(int j = i + 1; j < pante.size() && ok == true; ++j){
            if(pante[i].valoare != pante[j].valoare){
                ok = false;
            }
            else{
                ++num_trapeze;
            }
        }
    }
    out << num_trapeze;
    return 0;
}