Cod sursa(job #604783)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 25 iulie 2011 11:36:07
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <iostream>
#include <algorithm>

#define NMax 120005
#define Inf 2000000000

using namespace std;

typedef struct
{
    double x, y;
}
Coord;

Coord P[NMax];
int N, Stack[NMax], K;

inline bool cmp (Coord A, Coord B)
{
    if ((A.x-P[1].x)*(B.y-P[1].y)>(B.x-P[1].x)*(A.y-P[1].y))
    {
        return true;
    }
    return false;
}

void Read ()
{
    freopen ("infasuratoare.in", "r", stdin);
    scanf ("%d", &N);
    double XMin=Inf, YMin=Inf;
    int iMin=0;
    for (int i=1; i<=N; ++i)
    {
        scanf ("%lf %lf", &P[i].x, &P[i].y);
        if (P[i].x==XMin and P[i].y<YMin)
        {
            iMin=i;
            YMin=P[i].y;
        }
        if (P[i].x<XMin)
        {
            iMin=i;
            XMin=P[i].x;
            YMin=P[i].y;
        }
    }
    Coord Aux=P[1];
    P[1]=P[iMin];
    P[iMin]=Aux;
    sort (P+2, P+N+1, cmp);
}

void Print ()
{
    freopen ("infasuratoare.out", "w", stdout);
    printf ("%d\n", K);
    for (int i=1; i<=K; ++i)
    {
        printf ("%lf %lf\n", P[Stack[i]].x, P[Stack[i]].y);
    }
}

inline float Sign (Coord A, Coord B, Coord C)
{
    return A.x*B.y+B.x*C.y+C.x*A.y-B.y*C.x-C.y*A.x-A.y*B.x;
}

void ConvexHull ()
{
    Stack[1]=1;
    Stack[2]=2;
    K=2;
    int i=2;
    while (i<N)
    {
        ++i;
        while (K>1 and Sign (P[Stack[K]], P[Stack[K-1]], P[i])>0)
        {
            --K;
        }
        Stack[++K]=i;
    }
}

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