Cod sursa(job #1615685)

Utilizator BugirosRobert Bugiros Data 26 februarie 2016 19:19:54
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;

const int MAXN = 120005;
const double EPS = 1e-12;


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

struct punct
{
    double x,y;
};

bool ordine_buna(punct a, punct b)
{
    if (a.x < b.x)
        return true;
    if (a.x > b.x)
        return false;
    return a.y < b.y;
}

punct v[MAXN];
int n;

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

int stiva[MAXN];
int l_stiva = 0;
bool vizitat[MAXN];

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


void prelucrare()
{
    sort(v + 1, v + n + 1, ordine_buna);
    stiva[1] = 1;
    stiva[2] = 2;
    l_stiva = 2;
    vizitat[2] = true;
    for (int i = 1,sens = 1;i > 0;i += sens)
    {
        if (i == n)
            sens = -sens;
        if (vizitat[i])
            continue;
        while(l_stiva >= 2 && produs_vectorial(v[stiva[l_stiva - 1]], v[stiva[l_stiva]], v[i]) < EPS)
        {
            vizitat[stiva[l_stiva]] = false;
            --l_stiva;
        }
        stiva[++l_stiva] = i;
        vizitat[i] = true;
    }
}

void afisare()
{
    out << fixed;
    --l_stiva;
    out << l_stiva << '\n';
    out << setprecision(6);
    for (int i = 1;i <= l_stiva;++i)
        out << v[stiva[i]].x << ' ' << v[stiva[i]].y << '\n';
}

int main()
{
    citire();
    prelucrare();
    afisare();
    return 0;
}