Cod sursa(job #2883407)

Utilizator PopaMihaimihai popa PopaMihai Data 1 aprilie 2022 14:49:29
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>

using namespace std;

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

using ld = long double;
using PII = pair < ld, ld >;

const int NMAX = 12e4 + 3;

int N;
PII v[NMAX];
int st[NMAX];
bool sel[NMAX];

static inline void Read()
{
    fin >> N;
    for(int i = 1; i <= N; ++i)
        fin >> v[i].first >> v[i].second;

    return;
}

static inline ld Det(PII a, PII b, PII c)
{
    return (a.first * b.second + b.first * c.second + a.second * c.first
         - c.first * b.second - b.first * a.second - c.second * a.first);
}

static inline void Solve()
{
    sort(v + 1, v + N + 1);

    st[0] = 2;
    st[1] = 1;
    st[2] = 2;

    sel[1] = true;
    sel[2] = true;

    for(int i = 3; i <= N; ++i) {
        while(st[0] >= 2 && Det(v[i], v[st[st[0]]], v[st[st[0] - 1]]) <= 0)
            sel[st[st[0]--]] = false;
        st[++st[0]] = i;
        sel[i] = true;
    }
    sel[1] = false;
    for(int i = N; i > 0; --i) {
        if(sel[i] == true)
            continue;

        while(st[0] >= 2 && Det(v[i], v[st[st[0]]], v[st[st[0] - 1]]) <= 0)
            sel[st[st[0]--]] = false;
        st[++st[0]] = i;
        sel[i] = true;
    }
    fout << st[0] - 1 << '\n';

    fout << setprecision(12) << fixed;
    for(int i = st[0] - 1; i >= 1; --i) {
        fout << v[st[i]].first << " " << v[st[i]].second << '\n';
    }
    return;
}

int main()
{
    Read();
    Solve();
    return 0;
}