Cod sursa(job #2073928)

Utilizator ruxandramateiMatei Ruxandra ruxandramatei Data 23 noiembrie 2017 20:52:24
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.12 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#define DMAX 120001

using namespace std;

ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");

typedef struct {
   float x, y;
}PCT;

PCT puncte[DMAX],minim;
bool pus[DMAX];
int n;//date de intrare
int indMin;

PCT rezultat[DMAX];
int lgRez;

void citire(){
    in >> n;
    in >> puncte[1].x >> puncte[1].y;
    indMin = 1;
    minim = puncte[1];
    for(int i = 2; i <= n; i++){
        in >> puncte[i].x >> puncte[i].y;
        if(puncte[i].x < minim.x){
            minim = puncte[i];
            indMin = i;
        }
    }
}

//inmultirea a 2 vectori : ab, ac este pozitiva daca ab se afla in stanga lui ac
//altfel daca este 0 inseamna ca sunt coliniare
//altfel inseamna cl ab se afca in dreapta

long long inmultireVectori(PCT actual, PCT tinta, PCT verificat){
    long long x1 = actual.x - tinta.x;
    long long x2 = actual.x - verificat.x;
    long long y1 = actual.y - tinta.y;
    long long y2 = actual.y - verificat.y;

    return 1LL*y2*x1 -  1LL*y1*x2;
}

void rezolvare(){
    PCT start = minim;
    pus[indMin] = true;
    PCT curent = start;
    do{
        int pozInd;
        PCT tinta = curent;

        for(int i = 1; i <= n; i++){
            if(curent.x != puncte[i].x && curent.y != puncte[i].y ){
                tinta = puncte[i];
                pozInd = i;
                break;
            }
        }
        for(int i = 1; i <= n; i++){
            if(curent.x == puncte[i].x && curent.y == puncte[i].y || pus[i] == true){
                continue;
            }
            int inmultire = inmultireVectori(curent, tinta, puncte[i]);
            if(inmultire >= 0){
                tinta = puncte[i];
                pozInd = i;
            }
        }
        rezultat[++lgRez] = tinta;
        curent = tinta;
        pus[pozInd] = true;
    }while(curent.x != start.x || curent.y != start.y);
}

void afisare(){
    out << lgRez << '\n';
    out << setprecision(6) << fixed;
    for(int i = lgRez; i >= 1; i--){
        out << rezultat[i].x << ' ' << rezultat[i].y << '\n';
    }
}

int main() {
    citire();
    rezolvare();
    afisare();
    return 0;
}