Cod sursa(job #909910)

Utilizator TeodoraTanaseTeodora Tanase TeodoraTanase Data 10 martie 2013 17:56:30
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 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 poz;
int h = 2;
int q[NMAX];

bool cmp(punct a, punct b)
{
    return a.p < b.p;
}

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

    return y / x;
}

void read()
{
    int xmin = INF;
    int ymin = INF;

    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);

        if(a[i].x < xmin || a[i].x == xmin && a[i].y < ymin)
        {
            poz = i;
            xmin = a[i].x;
            ymin = a[i].y;
        }
    }

    swap(a[poz], a[n - 1]);
    -- n;
}

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

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] = n;
    q[1] = 0;

    for(int i = 1; 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();
    panta();
    sort(a, a + n, cmp);
    solve();
    write();

    return 0;
}