Cod sursa(job #2892484)

Utilizator lolotbogdanLolot Stefan-Bogdan lolotbogdan Data 22 aprilie 2022 12:41:59
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>

using namespace std;

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

struct punct{
    double x, y;
};

int n;
punct puncte[120001], stiva[120001];

bool comparaPuncte(const punct &P1, const punct P2){

    if(P1.x == P2.y)
        return P1.y < P2.y;
    return P1.x < P2.x;
}

double determinant(const punct &P1, const punct &P2, const punct &P3){
    return (P1.x - P2.x) * (P1.y - P3.y) - (P1.y - P2.y) * (P1.x - P3.x);
}

bool comparaDeterminant(const punct &P1, const punct &P2){
    return determinant(puncte[1], P1, P2) < 0;
}

void acoperire_convexa(){
    sort(puncte + 2, puncte + n + 1, comparaDeterminant);
    stiva[1] = puncte[1];
    stiva[2] = puncte[2];
    int varf = 2;

    for(int i = 3; i <= n; i++){
        while(varf >= 2 && determinant(stiva[varf - 1], stiva[varf], puncte[i]) > 0)
            varf--;
        stiva[++varf] = puncte[i];
    }

    g << varf << "\n";
    for(int i = varf; i >= 1; i--)
        g << fixed << setprecision(6) << stiva[i].x << " " << stiva[i].y << "\n";
}

int main(){

    f >> n;
    int pozMinim = 1;

    for(int i = 1; i <= n; i++){

        f >> puncte[i].x >> puncte[i].y;

        if(comparaPuncte(puncte[i], puncte[pozMinim]))
            pozMinim = i;
    }

    swap(puncte[1], puncte[pozMinim]);

    acoperire_convexa();

    return 0;
}