Cod sursa(job #3039527)

Utilizator lolismekAlex Jerpelea lolismek Data 28 martie 2023 17:37:47
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

#include <iomanip>

using namespace std;

string filename = "infasuratoare";

#ifdef LOCAL
    ifstream fin("input.in");
    ofstream fout("output.out");
#else
    ifstream fin(filename + ".in");
    ofstream fout(filename + ".out");
#endif

const int NMAX = 120000;

struct Point{
    double x, y;
}v[NMAX + 1];

bool cmp(Point a, Point b){
    if(a.x == b.x){
        return a.y > b.y;
    }
    return a.x < b.x;
}

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

signed main(){

    int n;
    fin >> n;

    for(int i = 1; i <= n; i++){
        fin >> v[i].x >> v[i].y;
    }

    sort(v + 1, v + n + 1, cmp);

    vector <int> up;
    up.push_back(1);

    for(int i = 2; i <= n; i++){
        while((int)up.size() > 1 && area(v[up[(int)up.size() - 2]], v[up.back()], v[i]) >= 0){
            up.pop_back();
        }
        up.push_back(i);
    }

    vector <int> down;
    down.push_back(1);

    for(int i = 2; i <= n; i++){
        while((int)down.size() > 1 && area(v[down[(int)down.size() - 2]], v[down.back()], v[i]) <= 0){
            down.pop_back();
        }
        down.push_back(i);
    }

    vector <int> ch = up;

    down.pop_back();
    reverse(down.begin(), down.end());
    down.pop_back();

    for(int x : down){
        ch.push_back(x);
    }

    reverse(ch.begin(), ch.end());

    fout << fixed << setprecision(12);

    fout << ch.size() << '\n';
    for(int ind : ch){
        fout << v[ind].x << ' ' << v[ind].y << '\n'; 
    }

    return 0;
}