Cod sursa(job #2194745)

Utilizator timar_andreiTimar Andrei timar_andrei Data 14 aprilie 2018 12:03:26
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

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

int N;
const int NMAX = 120005;
const double EPS = 1e-12;

pair<double,double> V[NMAX];
bool Use[NMAX];
int ST[NMAX];
int Front;

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

double product(pair<double,double> O,pair<double,double> A, pair<double,double> B)
{
    return (A.first - O.first) * (B.second - O.second) - (B.first - O.first) * (A.second - O.second);
}

int main()
{
    Read();

    sort(V+1,V+N+1);
    ST[1] = 1;
    ST[2] = 2;
    Front = 2;
    Use[2] = true;

    for(int i=1,p=1; i > 0; i+= (p = (i == N? -p : p)))
    {
        if (Use[i])continue;
        while(Front >= 2 && product(V[ST[Front-1]], V[ST[Front]],V[i]) < EPS)
            Use[ST[Front--]] = false;
        ST[++Front] = i;
        Use[i] = true;
    }

    fout<<Front - 1<<'\n';
    fout<<setprecision(6)<<fixed;
    for(int i=1;i<Front;i++)
    {
        fout<<V[ST[i]].first<<' '<<V[ST[i]].second<<'\n';
    }

    return 0;
}