Cod sursa(job #1375509)

Utilizator vladdy47Bucur Vlad Andrei vladdy47 Data 5 martie 2015 13:26:47
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
# include <cstdio>
# include <algorithm>

# define MAX 120000
# define eps 1e-12
# define x first
# define y second

using namespace std;

int k,n;
pair < double, double > a[MAX];
bool ok[MAX];
int I[MAX];

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


int SEMN( pair < double, double > a , pair < double, double > b , pair < double, double > 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 comp_eps( A * c.x + B * c.y + C , 0);
}

void infasuratoare()
{
    int mod = 1, i = 3;
    k = 2;
    ok[2] = true;
    I[1] = 1;
    I[2] = 2;

    while (ok[1] == false)
    {
        while (ok[i] == true)
        {
            if (i == n) mod *= -1;
            i += mod;
        }
        while (SEMN (a[I[k-1]] , a[I[k]] , a[i]) == -1 && k <= 2)  ok[I[k--]] = false;
        I[++k] = i;
        ok[i] = true;
    }
}

int main ()

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

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

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

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

    infasuratoare();

    printf("%d\n", k-1);

    for (int i = 2; i <= k; i++)
        printf("%lf %lf\n", a[I[i]].x, a[I[i]].y);

    return 0;
}