Cod sursa(job #2892474)

Utilizator lolotbogdanLolot Stefan-Bogdan lolotbogdan Data 22 aprilie 2022 11:59:23
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>

using namespace std;

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

int n, nr_puncte_infasuratoare_convexa;
int indice_minim;
pair<double, double>punct_minim;
vector<pair<double, double>>puncte;
vector<pair<double, double>>varfuri_acoperire;

double determinant(pair<double, double>p, pair<double, double> q, pair<double, double>r){
    return (q.second - p.second) * (r.first - q.first) - (q.first - p.first) * (r.second - q.second);
}

void acoperire_convexa(){
    int p = indice_minim;
    int q;


    do{
        varfuri_acoperire.push_back(puncte[p]);

        q = (p + 1) % n;

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

            if(determinant(puncte[p], puncte[i], puncte[q]) < 0)
                q = i;
        }

        p = q;

    }while(p != indice_minim);

    g << varfuri_acoperire.size() << "\n";

    for(int i = 0; i < varfuri_acoperire.size(); i++)
        g << fixed << setprecision(6) << varfuri_acoperire[i].first << " " << varfuri_acoperire[i].second << "\n";
}

int main(){
    f >> n;

    puncte.resize(n);

    for(int i = 0; i < n; i++){
        f >> puncte[i].first >> puncte[i].second;

        if(i == 0)
            punct_minim = puncte[i];

        else if (punct_minim.first > puncte[i].first){
            punct_minim = puncte[i];
            indice_minim = i;
        }
    }

    acoperire_convexa();

    return 0;
}