Cod sursa(job #1124039)

Utilizator StanAndreiAndrei Stan StanAndrei Data 26 februarie 2014 11:01:29
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <stdio.h>
#include <iomanip>
#include <algorithm>

#define NMAX 120005

#define x first
#define y second

using namespace std;

typedef pair<double,double> Points;

Points V[NMAX],STACK[NMAX],ST[NMAX];
int N,HEAD=2;

void read()
{
    scanf("%d\n",&N);

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

double cross_product(Points A,Points B,Points C)
{
    return (B.x-A.x)*(C.y-A.y) - (B.y-A.y)*(C.x-A.x);
}

int cmp(Points A,Points B)
{
    return cross_product(V[1],A,B)<0;
}

void sort_points()
{
    int poz=1;
    for (int i=2;i<=N;i++)
        if (V[i]<V[poz]) poz=i;

    swap(V[1],V[poz]);
    sort(V+2,V+N+1,cmp);
}

void convex_hull()
{
    sort_points();

    ST[1]=V[1];
    ST[2]=V[2];
    for (int i=3;i<=N;i++)
    {
        while (HEAD>=2 && cross_product(ST[HEAD-1],ST[HEAD],V[i])>0)
            HEAD--;
        ST[++HEAD]=V[i];
    }
}

void print_result()
{
    printf("%d\n",HEAD);
    for (int i=HEAD;i>=1;i--)
        printf("%lf %lf\n",ST[i].x,ST[i].y);
}

int main()
{
    freopen ("infasuratoare.in","r",stdin);
    freopen ("infasuratoare.out","w",stdout);

    read();
    convex_hull();
    print_result();

    fclose(stdin);
    fclose(stdout);
    return 0;
}