Cod sursa(job #1067305)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 26 decembrie 2013 17:48:16
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define x first
#define y second


#define Nmax 120005

int N;
pair<double, double> M[Nmax];
pair<double, double> S[Nmax];

int vf;

void read()
{
    scanf("%d",&N);
    for (int i = 1; i <= N; ++i)
        scanf("%lf %lf",&M[i].x,&M[i].y);
}

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

class cmp{
public:
    bool operator()(const pair<double,double> p1, const pair<double,double> p2) const
    {
        return cross_product(M[1], p1, p2) < 0;
    }
};

void sortare()
{
    int pz = 1;
    for (int i = 2; i <= N; ++i)
        if (M[i] < M[pz])
            pz = i;
    swap(M[1], M[pz]);
    sort(M + 2, M + N + 1, cmp());
}

void convex_hull()
{
    sortare();
    S[1] = M[1];S[2] = M[2];vf = 2;
    for (int i = 3; i <= N; ++i)
    {
        while (vf >= 2 && cross_product(S[vf - 1], S[vf], M[i]) > 0)
            --vf;
        S[++vf] = M[i];
    }
}

void afish()
{
    printf("%d\n",vf);
    for (int i = vf; i >= 1; --i)
        printf("%.6lf %.6lf\n",S[i].x,S[i].y );
}

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