Cod sursa(job #578357)

Utilizator AndrewTheGreatAndrei Alexandrescu AndrewTheGreat Data 11 aprilie 2011 11:16:48
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <utility>
#include <algorithm>
#define x first
#define y second

using namespace std;

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

int N;
pair<double, double> P[120100];
int S[120100], K, In[120100];

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

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

    sort( P + 1, P + 1 + N );

    S[1] = 1; S[2] = 2; K = 2;
    In[1] = In[2] = 1;

    i = 2;
    while(i > 1)
    {
        if(t > 0 && i < N)
            i += t;
        else {
            t = -1;
            while(In[i] && i > 1)
                i += t;
            if(i == 1)
                break;
        }

        while(K > 1 && semn(P[S[K]], P[S[K - 1]], P[i]) > 0)
            In[S[K]] = 0, --K;
        S[++K] = i;
        In[i] = 1;
    }

    printf("%d\n", K);
    for(i = 1; i <= K; i++)
        printf("%lf %lf\n", P[S[i]].x, P[S[i]].y);
    return 0;
}