Cod sursa(job #803919)

Utilizator socheoSorodoc Ionut socheo Data 28 octombrie 2012 16:16:07
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <cstdio>
#include <algorithm>

using namespace std;

struct Punct{
    double x;
    double y;
}p[120002];

Punct q[120002];
bool dupa_x(Punct a, Punct b)
{
    if(a.x < b.x || (a.x == b.x && a.y < b.y))
        return 1;
    return 0;
}
int intoarce(Punct a , Punct b, Punct c)
{
    if((b.x * c.y + a.x * b.y + c.x * a.y - a.y * b.x - c.x * b.y - a.x * c.y) >= 0)
        return 1;
    else
        return 0;
}
int n;
int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    scanf("%d",&n);
    for(int i = 1; i <= n; i++)
    {
      scanf("%lf%lf", &p[i].x, &p[i].y);
    }
    sort(p + 1, p + n + 1, dupa_x);
    q[1].x = p[1].x;
    q[1].y = p[1].y;
    int h = 1;
    for(int i = 2; i <= n; i++)
    {
        while(h > 1 && !intoarce(q[h - 1], q[h], p[i]))
            h = h - 1;
        h = h + 1;
        q[h].x = p[i].x;
        q[h].y = p[i].y;

    }
    for(int  i = n - 1; i >= 1; i--)
    {
        while(!intoarce(q[h - 1], q[h], p[i]))
            h = h - 1;
        h = h + 1;
        q[h].x = p[i].x;
        q[h].y = p[i].y;

    }
    h = h - 1;
    printf("%d\n", h);
    for(int  i = 1; i <= h ; i++)
    {
        printf("%.6lf %.6lf\n", q[i].x, q[i].y);
    }


    return 0;
}