Cod sursa(job #630079)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 4 noiembrie 2011 18:11:59
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <cstdio>
#include <algorithm>

#define NMax 120005
#define x first
#define y second

using namespace std;

pair <double, double> P[NMax];
int N, M, K, S[NMax];

void Read ()
{
    freopen ("infasuratoare.in", "r", stdin);
    scanf ("%d", &N);
    M=1;
    for (int i=1; i<=N; ++i)
    {
        scanf ("%lf %lf", &P[i].x, &P[i].y);
        if (P[i].x==P[M].x)
        {
            if (P[i].y<P[M].y)
            {
                M=i;
            }
        }
        if (P[i].x<P[M].x)
        {
            M=i;
        }
    }
}

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

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

inline double Angle (pair <double, double> A, pair <double, double> B, pair <double, double> C)
{
    return A.x*B.y+B.x*C.y+C.x*A.y-B.y*C.x-A.y*B.x-A.x*C.y;
}

inline void Push (int i)
{
    S[++K]=i;
}

inline void Pop ()
{
    S[K--]=0;
}

void ConvexHull ()
{
    swap (P[M], P[1]);
    sort (P+2, P+N+1, Compare);
    Push (1);
    Push (2);
    for (int i=3; i<=N; ++i)
    {
        while (K>1 and Angle (P[S[K]], P[S[K-1]], P[i])<=0)
        {
            Pop ();
        }
        Push (i);
    }
}

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