Cod sursa(job #2157454)

Utilizator filip.mihalutMihalut Filip filip.mihalut Data 9 martie 2018 17:14:10
Problema Infasuratoare convexa Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <bits/stdc++.h>
#define Nmax 120005

using namespace std;

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

struct filip
{
    double x,y;
} v[Nmax];

int i,n;
stack < int > st;
int seen[Nmax],semn = 1,nr;

double arie(int a,int b,int c)
{
    return v[a].x * v[b].y + v[b].x * v[c].y + v[c].x * v[a].y -
           v[c].x * v[b].y - v[a].x * v[c].y - v[b].x * v[a].y;
}

bool cmp(filip a,filip b)
{
    if(a.y == b.y)
        return a.x < a.y;
    return a.y < b.y;
}

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

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

    st.push(1);
    st.push(2);
    seen[2] = 1;

    for(i = 3; i >= 1; i += semn)
        if(not seen[i])
        {
           nr = st.top();
           st.pop();
           while(not st.empty() && arie(nr,st.top(),i) < 0)
           {
               seen[nr] = 0;
               nr = st.top();
               st.pop();
            }
            st.push(nr);
            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()].x << " " << v[st.top()].y << '\n';
        st.pop();
    }
    return 0;
}