Cod sursa(job #1095786)

Utilizator gabrielvGabriel Vanca gabrielv Data 31 ianuarie 2014 21:18:57
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define NMAX 120005

struct Point
{
    double x,y;
};

Point V[NMAX];
Point Queue[NMAX];

int N;
int QVaf;

void Read()
{
    freopen("infasuratoare.in","r",stdin);
    scanf("%d",&N);

    for(int i=1;i<=N;i++)
        scanf("%lf%lf",&V[i].x,&V[i].y);

}

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

bool cmp(Point i, Point j)
{
    return determinant(V[1],i,j) < 0;
}

void Solve()
{
    for(int i=2;i<=N;i++)
        if(V[i].y < V[1].y || (V[i].y == V[i].y && V[i].x < V[1].x))
            swap(V[0],V[i]);

    sort(V+2,V+N+1,cmp);

    Queue[1] = V[1];
    Queue[2] = V[2];
    QVaf = 2;

    for(int i=3;i<=N;i++)
    {
        while(QVaf>=2 && determinant(Queue[QVaf-1],Queue[QVaf],V[i]) > 0)
            QVaf--;

        Queue[++QVaf] = V[i];
    }
}

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

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

int main()
{
    Read();
    Solve();
    Print();
    return 0;
}