Cod sursa(job #3359140)

Utilizator Car13Carmi Carabas Car13 Data 25 iunie 2026 03:59:34
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

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

double directie(double ax, double ay, double bx, double by, double cx, double cy){
    double p = (bx - ax) * (cy - ay) - (by - ay) * (cx - ax);
    return p;
}

int main(){
    int i, n;
    fin >> n;
    vector <pair<double , double>> puncte(n);
    vector <pair <double, double>> stiva;
    for(i = 0; i < n; i++){
        fin >> puncte[i].first >> puncte[i].second;
    }
    sort(puncte.begin(), puncte.end());
    stiva.push_back(puncte[0]);
    for(i = 1; i < n; i++){
        while(stiva.size() >= 2 && directie(stiva[stiva.size() - 2].first, stiva[stiva.size() - 2].second, stiva[stiva.size() - 1].first, stiva[stiva.size() - 1].second, puncte[i].first, puncte[i].second) <= 1e-12){
            stiva.pop_back();
        }
        stiva.push_back(puncte[i]);
    }
    int k = stiva.size();
    for(i = n - 2; i >= 0; i--){
        while(stiva.size() >= k + 1 && directie(stiva[stiva.size() - 2].first, stiva[stiva.size() - 2].second, stiva[stiva.size() - 1].first, stiva[stiva.size() - 1].second, puncte[i].first, puncte[i].second) <= 1e-12){
            stiva.pop_back();
        }
        stiva.push_back(puncte[i]);
    }
    fout << stiva.size() - 1 << endl;
    fout << fixed << setprecision(6);
    for(i = 0; i < stiva.size() - 1; i++){
        fout << stiva[i].first << " " << stiva[i].second << endl;
    }
    fin.close();
    fout.close();
    return 0;
}