Cod sursa(job #2710132)

Utilizator As932Stanciu Andreea As932 Data 21 februarie 2021 21:36:29
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#define per pair<double,double>
#define x first
#define y second

using namespace std;

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

const int nmx = 12e4 + 5;

int n, top;
per v[nmx], st[nmx];

void read(){
    cin >> n;

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

void minim(){
    int mn = 1;

    for(int i = 2; i <= n; i++)
        if(v[i] < v[mn])
            mn = i;

    swap(v[1], v[mn]);
}

double cross_prod(per a, per b, per c){
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

bool cmp(per a, per b){
    return cross_prod(v[1], a, b) < 0;
}

void solve(){
    st[1] = v[1];
    st[2] = v[2];
    top = 2;

    for(int i = 3; i <= n; i++){
        while(top >= 2 && cross_prod(st[top - 1], st[top], v[i]) > 0)
            --top;
        st[++top] = v[i];
    }
}

void print(){
    cout << top << "\n";
    for(int i = top; i >= 1; i--)
        cout << fixed << setprecision(9) << st[i].x << " " << st[i].y << "\n";
}

int main()
{
    read();
    minim();
    sort(v + 2, v + n + 1, cmp);
    solve();
    print();

    return 0;
}