Cod sursa(job #613372)

Utilizator TeodoraTanaseTeodora Tanase TeodoraTanase Data 22 septembrie 2011 19:23:25
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <cstdio>
#include <algorithm>
#define N 120005
#define inf 1000000005

using namespace std;

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

int h, n = 2, poz;

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

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

void afisare()
{
    printf ("%d\n", n);
    for (int i = 0; i < n; ++ i)
        printf ("%lf %lf\n", s[i].x, s[i].y);
}

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

bool determinant(punct a, punct b, punct c)
{
    double det = 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 (det >= 0)
        return true;
    return false;
}

void infasuratoare()
{
    s[0] = x;
    s[1] = a[0];
    for (int i = 1; i < h; ++ i)
        if (determinant (s[n-2], s[n-1], a[i]))
            s[n ++] = a[i];
        else
        {
            while (!determinant (s[n-2], s[n-1], a[i]))
                s[-- n] = a[i];
            ++ n;
        }
}

int main()
{
    freopen ("infasuratoare.in", "r", stdin);
    freopen ("infasuratoare.out", "w", stdout);
    citire();
    panta();
    sort(a, a+h, cmp);
    infasuratoare();
    afisare();
    return 0;
}