Cod sursa(job #909855)

Utilizator TeodoraTanaseTeodora Tanase TeodoraTanase Data 10 martie 2013 17:39:49
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <cstdio>
#include <algorithm>

#define NMAX 120002
#define INF (1 << 30)

using namespace std;

struct punct
{
    double x;
    double y;
    double p;
}a[NMAX];

int n;
int h = 2;
int q[NMAX];

bool cmp(punct a, punct b)
{
    if(a.p < b.p || a.p == b.p && a.y > b.y)
        return 1;

    return 0;
}

double panta(double x, double y)
{
    if(x == 0)
        return INF;

    return y / x;
}

void read()
{
    freopen("infasuratoare.in", "r", stdin);

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

    for(int i = 0; i < n; ++ i)
    {
        scanf("%lf %lf\n", &a[i].x, &a[i].y);
        a[i].p = panta(a[i].x, a[i].y);
    }
}

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

void solve()
{
    q[0] = 0;
    q[1] = 1;

    for(int i = 2; i < n; ++ i)
    {
        while(det(a[q[h - 2]], a[q[h - 1]], a[i]) <= 0)
            -- h;

        q[h ++] = i;
    }
}

void write()
{
    freopen("infasuratoare.out", "w", stdout);

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

    for(int i = 0; i < h; ++ i)
        printf("%lf %lf\n", a[q[i]].x, a[q[i]].y);
}

int main()
{
    read();
    sort(a, a + n, cmp);
    solve();
    write();

    return 0;
}