Cod sursa(job #1915715)

Utilizator filip.mihalutMihalut Filip filip.mihalut Data 8 martie 2017 22:13:11
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <algorithm>
#include <iomanip>

using namespace std;

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

pair < double,double > v[120005];
stack < int > st;
bool seen[120005],ok;
int x,n,i;

int det(pair < int,int >  a,pair < int,int >  b,pair < int,int >  c)
{
    return b.second*c.first + c.second*a.first + a.second*b.first - a.first*b.second - b.first*c.second - c.first*a.second;
}

int main()
{
    f >> n;
    for(i = 1; i <= n; i++)
        f >> v[i].second >> v[i].first;

    sort(v + 1,v + n + 1);

    st.push(1);
    st.push(2);
    seen[2] = 1;
    i = 2;
    while(i > 1)
    {
        if(not seen[i])
        {
            x = st.top();
            st.pop();
            while(st.top() != 1 && det(v[x],v[st.top()] , v[i]) < 0)
                seen[x] = 0,x = st.top(),st.pop();
            st.push(x);
            st.push(i);
            seen[i] = 1;
        }

        if(i == n)
            ok = true;

        if(not ok)
            i++;
        else i--;
    }
    n = st.size();
    g << st.size() << '\n';
    g << fixed << setprecision(6);
    g << v[1].second << " " << v[1].first << '\n';
    while(n > 1)
        g  << v[st.top()].second << " " << v[st.top()].first  << '\n' , st.pop() ,n--;
    return 0;
}