Cod sursa(job #1687399)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 12 aprilie 2016 20:39:13
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <bits/stdc++.h>

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

#define eps 1e-12

using namespace std;

const int nmax = 1 << 17;

int n , i;
bool in[nmax];
point a[nmax];

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)
{
    double sum = 0;
    sum += a.x * b.y + b.x * c.y + a.y * c.x;
    sum -= b.y * c.x + b.x * a.y + a.x * c.y;
    return compare(sum , 0);
}

void convexhull()
{
    int act = 3, mode = 1;
    vector < int > st;

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

    while (!in[1])
    {
        while (in[act])
        {
            if (act == n) mode *= -1;
            act += mode;
        }

        while (st.size() > 1 && semn(a[st[st.size()-2]] , a[st[st.size()-1]] , a[act]) == 1)
            in[st.back()] = 0, st.pop_back();

        st.push_back(act); in[act] = 1;
    }

    st.pop_back();
    for (printf("%d\n", (int)st.size()); st.size(); st.pop_back())
        printf("%f %f\n", a[st.back()].x , a[st.back()].y);
}

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

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

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

    convexhull();

    return 0;
}