Cod sursa(job #1374955)

Utilizator Theodor1000Cristea Theodor Stefan Theodor1000 Data 5 martie 2015 11:32:04
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <cstdio>
#include <algorithm>
#include <stack>

#define f first
#define s second

using namespace std;

stack <int> st;

pair <double, double> v[120010];
bool frq[120010];

bool det (pair <double, double> a, pair <double, double> b, pair <double, double> c)
{
    double d = 1.0 * a.f * b.s + 1.0 * b.f * c.s + 1.0 * a.s * c.f - 1.0 * c.f * b.s - 1.0 * b.f * a.s - 1.0 * c.s * a.f;
    return (d < 0.0);
}

int main ()
{
    freopen ("infasuratoare.in", "r", stdin);
    freopen ("infasuratoare.out", "w", stdout);

    int n;
    scanf ("%d", &n);

    for (int i = 1; i <= n; ++i)
        scanf ("%lf %lf", &v[i].f, &v[i].s);

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

    st.push (1);
    st.push (2);
    frq[2] = true;

    for (int i = 3; i <= n;)
    {
        int b = st.top ();
        st.pop ();
        int a = st.top ();
        st.push (b);

        if (det (v[a], v[b], v[i]))
        {
            st.push (i);
            frq[i++] = true;
        }

        else frq[b] = false, st.pop ();
    }

    for (int i = n - 1; i;)
    {
        if (frq[i])
        {
            --i;
            continue;
        }

        int b = st.top ();
        st.pop ();
        int a = st.top ();
        st.push (b);

        if (det (v[a], v[b], v[i])) st.push (i--);
        else st.pop ();
    }

    st.pop ();
    printf ("%d\n", st.size ());

    while (!st.empty ())
    {
        pair <double, double> a = v[st.top ()];
        st.pop ();

        printf ("%lf %lf\n", a.f, a.s);
    }

    return 0;
}