Cod sursa(job #3359001)

Utilizator Andrei-Dani-10Pisla Andrei Daniel Andrei-Dani-10 Data 22 iunie 2026 20:10:30
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>

#include <utility>
#define x first
#define y second

#include <algorithm>
#include <iomanip>

using namespace std;

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

typedef pair <double, double> pdd;
const int nmax = 120000;
int n, stktopp; pdd a[nmax + 2], stk[nmax + 2];

int crossproduct(pdd a0, pdd a1, pdd a2){
    return (a1.x - a0.x) * (a2.y - a0.y) - (a2.x - a0.x) * (a1.y - a0.y);
}

int main(){

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

    for(int i = 2; i <= n; i++){
        if(a[1] < a[i]){
            swap(a[1], a[i]);
        }
    }

    sort(a + 2, a + 1 + n, [](pdd a0, pdd a1){
        return (crossproduct(a[1], a0, a1) < 0);
    });

    stk[++stktopp] = a[1];
    stk[++stktopp] = a[2];

    for(int i = 3; i <= n; i++){
        for(; stktopp >= 2 && crossproduct(stk[stktopp - 1], stk[stktopp], a[i]) > 0; stktopp--);
        stk[++stktopp] = a[i];
    }

    out<<stktopp<<"\n";
    for(int i = stktopp; i >= 1; i--){
        out<<fixed<<setprecision(10)<<stk[i].x<<" "<<stk[i].y<<"\n";
    }

    return 0;
}