Cod sursa(job #875139)

Utilizator andreea29Iorga Andreea andreea29 Data 9 februarie 2013 19:03:58
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2 kb
#include<algorithm>
#include<cmath>
#include<cstdio>

#define Nmax 120010
#define Num 10000000

using namespace std;

int n, st[Nmax], viz[Nmax], k;

struct punct
{
    double x;
    double y;
} p[Nmax];

int cmp (punct a, punct b)
{
    if (a.x > b.x || (a.x == b.x && a.y > b.y))
        return 0;
    return 1;
}

/*double dist (punct a, punct b)
{
    return sqrt (double ((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)));
}*/

double det (punct a, punct b, punct c)
{
    return (a.x * b.y + b.x * c.y + c.x * a.y) - (a.y * b.x + b.y * c.x + c.y * a.x);
}

int semn (punct a, punct b, punct c)
{
    double d = det (a, b, c);
    if(fabs(d) < 0.0000000001)
        return 0;
    if (d > 0)
        return 1;
    else
        return 2;
}

void convex ()
{
    st[0] = 0;
    st[1] = 1;
   // st[2] = 2;
    viz[1] = 1;//viz[2] = 1;
    int s = 1;
    k = 1;
    int i = 2;
    while (i < n)
    {
        int s1 = semn (p[st[k - 1]], p[st[k]], p[i]);
        while (s != s1 && s1 != 0)
        {
            viz[st[k]] = 0;
            --k;
            s1 = semn (p[st[k - 1]], p[st[k]], p[i]);
        }
        ++k;
        st[k] = i;
        viz[i] = 1;
        ++i;
    }
    --i;
    while (i >= 0)
    {
        while (viz[i] && i >= 0)
            --i;
        if (i < 0)
            break;
        int s1 = semn (p[st[k - 1]], p[st[k]], p[i]);
        while (s != s1 && s1 != 0)
        {
            --k;
            s1 = semn (p[st[k - 1]], p[st[k]], p[i]);
        }
        ++k;
        st[k] = i;
        --i;
    }
}

int main()
{
    freopen ("infasuratoare.in", "r", stdin);
    freopen ("infasuratoare.out", "w", stdout);
    scanf ("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf ("%lf %lf", &p[i].x, &p[i].y);

    sort (p, p + n, cmp);

    convex ();

    printf ("%d\n", k);
    for (int i = 0; i < k; ++i)
    {
        printf ("%.13lf %.13lf\n", p[st[i]].x, p[st[i]].y);
    }
    return 0;
}