Cod sursa(job #1536232)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 25 noiembrie 2015 20:50:03
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <bits/stdc++.h>

#define point pair < double , double >
#define x first
#define y second

using namespace std;

const int Nmax = 120000 + 10;
const int eps = 1e-12;

int n , i;
point p[Nmax];

bool ok[Nmax];

vector < int > st;

int compare(double a , double b)
{
    if (a + eps < b) return -1;
    if (b + eps < a) return 1;
    return 0;
}

int semn(point a , point b , point c)
{
    ///determinant
    double sum = 0;
    sum += a.x*b.y + b.x*c.y + a.y*c.x;
    sum -= c.x*b.y + b.x*a.y + a.x*c.y;

    return compare(sum , 0);
}

void cevaCorect()
{
    int mod = 1 , crt = 3;

    st.push_back(1); st.push_back(2); ok[2] = 1;

    while (!ok[1])
    {
        while (ok[crt])
        {
            if (crt == n) mod = -1;
            crt += mod;
        }

        while (st.size() > 1 && semn(p[st[st.size()-2]] , p[st[st.size()-1]] , p[crt]) == 1)
            ok[st.back()] = 0, st.pop_back();
        st.push_back(crt); ok[crt] = 1;
    }
}

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

    scanf("%d", &n);
    for (i = 1; i <= n; ++i)
        scanf("%lf %lf", &p[i].x, &p[i].y);
    sort(p + 1 , p + n + 1);

    cevaCorect();

    for (printf("%d\n", st.size()-1) ; st.size() > 1; st.pop_back())
        printf("%f %f\n", p[st.back()].x , p[st.back()].y);

    return 0;
}