Cod sursa(job #1058788)

Utilizator mvcl3Marian Iacob mvcl3 Data 15 decembrie 2013 21:09:05
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

#define in "infasuratoare.in"
#define out "infasuratoare.out"
#define POINT pair < double, double >
#define x first
#define y second
#define Max_Size 120004

std :: ifstream f(in);
std :: ofstream g(out);

int N, Sol[Max_Size];
std :: POINT A[Max_Size];

inline void Read_Data()
{
    int poz = 1;

    f >> N;

    for(int i = 1; i <= N; ++i)
    {
        f >> A[i].x >> A[i].y;
        if(A[i] < A[poz])   poz = i;
    }

    std :: swap(A[poz], A[1]);
}

inline double det(std :: POINT a, std :: POINT b, std :: POINT c)
{
    return a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - a.x * c.y - b.x * a.y;
}

struct cmp
{
    bool operator () (const std :: POINT &a, const std :: POINT &b)
    {
        if(det(A[1], a, b) < 0) return 1;

        return 0;
    };
};

inline void Solve()
{
    for(int i = 1; i <= N; ++i)
    {
        while(Sol[0] >= 2 && det(A[ Sol[ Sol[0] - 1]], A[ Sol[ Sol[0]] ], A[i]) > 0)
            Sol[0]--;

        Sol[ ++Sol[0] ] = i;
    }
}

inline void Write_Data()
{
    g << Sol[0] << '\n';

    g << std :: fixed << std :: setprecision(6);

    for(int i = Sol[0]; i; --i) g << A[ Sol[i] ].x << ' '  << A[ Sol[i] ].y << '\n';
}

int main()
{
    Read_Data();
    std :: sort (A + 2, A + N + 1, cmp());
    Solve();
    Write_Data();

    //for(int i = 1; i <= N; ++i) g << A[i].x << ' '  << A[i].y << '\n';
    return 0;
}