Cod sursa(job #613358)

Utilizator TeodoraTanaseTeodora Tanase TeodoraTanase Data 22 septembrie 2011 14:00:59
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#include <cstdio>
#include <algorithm>
#define N 120005
#define inf 1000000005

using namespace std;

struct punct
{
    double x, y, p;
} a[N], c, st[N];

int n, poz;

bool cmp(punct a, punct b)
{
    if (a.p > b.p)
        return false;
    return true;
}

void citire()
{
    scanf ("%d ", &n);
    c.x = c.y = inf;
    for (int i = 0; i < n; ++ i)
    {
        scanf ("%lf %lf ", &a[i].x, &a[i].y);
        if (a[i].x < c.x || a[i].x == c.x && a[i].y < c.y)
        {
            c.x = a[i].x;
            c.y = a[i].y;
            poz = i;
        }
    }
    a[poz] = a[n-1];
    -- n;
}

void pante()
{
    for (int i = 0; i < n; ++i)
    {
        if (a[i].x == c.x)
            a[i].p = inf;
        else
            a[i].p = (a[i].y - c.y) / (a[i].x - c.x);
    }
}

bool det(punct a, punct b, punct c)
{
    double rez = a.x * b.y + a.y * c.x + b.x * c.y - a.y * b.x - b.y * c.x - c.y * a.x;
    if (rez >= 0)
        return true;
    return false;
}

void stiva()
{
    st[0] = c;
    st[1] = a[0];
    int m = 2;
    for (int i = 1; i < n; ++ i)
    {
        bool x = det (st[m-2], st[m-1], a[i]);
        if (x)
            st[m ++] = a[i];
        else
        {
            while(!det (st[m-2], st[m-1], a[i]))
                st[-- m] = a[i];
            ++ m;
        }
    }
    printf ("%d\n", m);
    for (int i = 1; i < m; ++ i)
        printf ("%lf %lf\n", st[i].x, st[i].y);
    printf ("%lf %lf\n", c.x, c.y);
}

int main()
{
    freopen ("infasuratoare.in", "r", stdin);
    ///freopen ("infasuratoare.out", "w", stdout);
    citire();
    pante();
    sort (a, a+n, cmp);
    stiva();
    return 0;
}