Cod sursa(job #2074640)

Utilizator ruxandramateiMatei Ruxandra ruxandramatei Data 24 noiembrie 2017 20:46:30
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>

#define DMAX 120001

using namespace std;

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

typedef struct {
    double x, y;
}PCT;

PCT puncte[DMAX];
int n;//date de intrare

int vfStiva;
PCT stivaRez[DMAX];

PCT minim;
int pozMinim;

void citire(){
    in >> n;
    in >> puncte[1].x >> puncte[1].y;
    minim = puncte[1];
    pozMinim = 1;
    for(int i = 2; i <= n; i++){
        in >> puncte[i].x >> puncte[i].y;
        if(puncte[i].y < minim.y || (puncte[i].y == minim.y && puncte[i].x < minim.x)){
            minim = puncte[i];
            pozMinim = 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

double inmultireVectori(PCT a, PCT b, PCT c){
    return  (double) a.x*b.y+b.x*c.y+c.x*a.y-b.y*c.x-c.y*a.x-a.y*b.x;
}


bool compar(PCT a, PCT b) {
    if (inmultireVectori(puncte[1], a, b) >= 0)
        return true;
    return false;
}

void rezolvare(){
    stivaRez[1] = minim;
    minim = puncte[1];
    puncte[1] = puncte[pozMinim];
    puncte[pozMinim] = minim;
    sort(puncte + 2, puncte + 1 + n, compar);
    stivaRez[2] = puncte[2];
    puncte[++n] = puncte[1];
    vfStiva = 2;
    for(int i = 3; i <= n; i++){
        while( vfStiva >= 2 && inmultireVectori(stivaRez[vfStiva - 1], stivaRez[vfStiva], puncte[i]) < 0){
            vfStiva --;
        }
        stivaRez[++vfStiva] = puncte[i];
    }
    vfStiva--;
}

void afisare(){
    out << vfStiva << '\n';
    out<<setprecision(13) << fixed;
    for(int i = 1; i <= vfStiva; i++){
        out << stivaRez[i].x << ' ' << stivaRez[i].y << '\n';
    }
}

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