Cod sursa(job #1375248)

Utilizator Theodor1000Cristea Theodor Stefan Theodor1000 Data 5 martie 2015 12:47:18
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.72 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);
}

bool det2 (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;

    bool OK = 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;
            OK = false;
        }

        else if (OK) ++i;
        else frq[b] = false, st.pop ();
    }

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

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

            //else if (OK) ++i;
            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 (det2 (v[a], v[b], v[i])) st.push (i--);
            else st.pop ();
        }
    }

    else
        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;
}