Cod sursa(job #2145948)

Utilizator filip.mihalutMihalut Filip filip.mihalut Data 27 februarie 2018 18:28:12
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>
#define Nmax 120005

using namespace std;

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

pair < double,double > v[Nmax];
stack < int > st;
int n,i,seen[Nmax],x,semn = 1;

bool cmp(pair < double,double > a, pair < double,double > b)
{
    if(a.second == b.second)
        return a.first < b.first;
    return a.second < b.second;
}

double arie(int x,int y,int z)
{
    return v[x].first*v[y].second + v[y].first*v[z].second + v[z].first*v[x].second -
           v[z].first*v[y].second - v[x].first*v[z].second - v[y].first*v[x].second;
}

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

    st.push(1);
    st.push(2);
    seen[2] = 1;
    for(i = 3; i > 0; i += semn)
    {
        if(seen[i])
            continue;
        x = st.top(); st.pop();
        while(not st.empty() && arie(x,st.top(),i) < 0)
        {
            seen[x] = 0;
            x = st.top();
             st.pop();
        }
        st.push(x);
        seen[i] = 1;
        st.push(i);
        if(i == n)
            semn = -1;
    }

    g << st.size() - 1 << '\n';
    while(st.size() > 1)
    {
        g << fixed << setprecision(6) << v[st.top()].first << " " << v[st.top()].second << '\n';
        st.pop();
    }
    return 0;
}