Cod sursa(job #932222)

Utilizator tsubyRazvan Idomir tsuby Data 28 martie 2013 19:33:45
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <cstdio>
#include <algorithm>
#define N 120005
using namespace std;

struct pct {
    double x,y;
};

int n, s[N], h;
pct puncte[N];
bool viz[N];

bool cmp(pct x, pct y)
{
    if (x.x == y.x)
    {
        if (x.y < y.y)
            return true;
        return false;
    }
    if (x.x < y.x)
        return true;
    return false;
}

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

void afisare()
{
    printf("%d\n", h);
    for(int i=h-1; i>=0; i--)
        printf("%.6lf %.6lf\n", puncte[s[i]].x, puncte[s[i]].y);
}

void citire()
{
    freopen("infasuratoare.in","rt",stdin);
    freopen("infasuratoare.out","wt",stdout);
    scanf("%d", &n);
    for (int i=0; i<n; i++)
        scanf("%lf %lf", &puncte[i].x, &puncte[i].y);
}

void infasor()
{
    s[0]=0, s[1]=1, h=1;
    viz[1]=1;
    int q=1; /// pas
    for (int i=2; !viz[0];)
    {
        while (viz[i])
        {
            if (i==n-1)
                q=-1;
            i+=q;
        }
        while (h>0 && ecuatia(puncte[s[h-1]], puncte[s[h]], puncte[i])>0)
            viz[s[h--]]=0;
        s[++h]=i;
        viz[i]=1;
    }
}
int main ()
{
    citire();
    sort(puncte, puncte+n, cmp);
    infasor();
    afisare();
    return 0;
}