Cod sursa(job #1339744)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 11 februarie 2015 08:55:28
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <cstdio>
#include <algorithm>

#define Nmax (120000 + 10)
#define eps 1e-12

#define punct pair < double , double >
#define X first
#define Y second

using namespace std;

punct p[Nmax];

int S[Nmax];

bool ok[Nmax];

int i , n , h;

int comparare(double A , double B)
{
    if (A + eps < B) return -1;

    if (B + eps < A) return 1;

    return 0;
}

int semn(punct a , punct b , punct c)
{
    double A , B , C;

    A = a.Y - b.Y;
    B = b.X - a.X;
    C = a.X * b.Y - b.X * a.Y;

    return comparare(A * c.X + B * c.Y + C , 0);
}

void infasuratoare()
{
    int k = 0 , mod = 1 , i = 3;

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

    S[++k] = 1; S[++k] = 2; ok[2] = true;

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

        while (k >= 2 && semn(p[S[k-1]] , p[S[k]] , p[i]) == -1)
            ok[ S[k--] ] = false;

        S[++k] = i; ok[i] = true;
    }

    h = k - 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);

    infasuratoare();

    printf("%d\n", h);

    for (i = 2; i <= h + 1; ++i)
     printf("%lf %lf\n", p[S[i]].X , p[S[i]].Y);

    return 0;
}