Cod sursa(job #3219300)

Utilizator catalinmarincatalinmarin catalinmarin Data 30 martie 2024 17:51:54
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <stack>
#include <vector>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct{
    long double x;
    long double y;
};
vector<punct> puncte;
vector<punct> stiva_jos;
vector<punct> stiva_sus;
bool compare(punct a, punct b){
    if (a.x == b.x)
        return a.y <= b.y;
    return a.x <= b.x;
}
long double arie(punct a, punct b, punct c){
    return a.x * b.y + b.x * c.y + c.x * a.y - b.y * c.x - c.y * a.x - a.y * b.x;
}
int main(){
    int n;
    fin >> n;
    for (int i = 0; i < n; i++){
        punct z;
        fin >> z.x >> z.y;
        puncte.push_back(z);
    }
    sort(puncte.begin(), puncte.end(), compare);
    stiva_jos.push_back(puncte[0]);
    for (int i = 1; i < n; i++){
        int sz = stiva_jos.size() - 1;
        while (stiva_jos.size() >= 2 && arie(stiva_jos[sz], stiva_jos[sz - 1], puncte[i]) > 0){
            stiva_jos.pop_back();
            sz--;
        }
        stiva_jos.push_back(puncte[i]);
    }
    stiva_sus.push_back(puncte[0]);
    for (int i = 1; i < n; i++){
        int sz = stiva_sus.size() - 1;
        while (stiva_sus.size() >= 2 && arie(stiva_sus[sz], stiva_sus[sz - 1], puncte[i]) < 0){
            stiva_sus.pop_back();
            sz--;
        }
        stiva_sus.push_back(puncte[i]);
    }
    fout << stiva_jos.size() + stiva_sus.size() - 2 << '\n';
    for (int i = 0; i < stiva_jos.size() - 1; i++){
        fout << fixed << setprecision(6) << stiva_jos[i].x << " ";
        fout << fixed << setprecision(6) << stiva_jos[i].y << " ";
        fout << '\n';
    }
    for (int i = stiva_sus.size() - 1; i > 0; i--){
        fout << fixed << setprecision(6) << stiva_sus[i].x << " ";
        fout << fixed << setprecision(6) << stiva_sus[i].y << " ";
        fout << '\n';
    }
    return 0;
}