Cod sursa(job #1374382)

Utilizator cosmin.pascaruPascaru Cosmin cosmin.pascaru Data 5 martie 2015 08:46:42
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

#define EPS 0.00000000001
#define NMAX 120005
#define x first
#define y second
#define Punct pair <double, double>
using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

Punct P[NMAX], S[NMAX];

inline double cross(Punct p0, Punct p, Punct q)
{
    return (((p.x - p0.x) * (q.y - p0.y)) - ((q.x - p0.x) * (p.y - p0.y)));
}
bool cmp(Punct p, Punct q)
{
    return (cross(P[0], p, q) < 0);
}
int main()
{
    int n;
    fin >> n;
    for (int i = 0; i < n; ++i)
        fin >> P[i].x >> P[i].y;

    int imin = 0;
    for (int i = 1; i < n; ++i)
        if (P[i].x < P[imin].x) imin = i;
        else if (P[i].x == P[imin].x && P[i].y < P[imin].y) imin = i;
    if (imin > 0) swap(P[0], P[imin]);

    sort(P + 1, P + n, cmp);

    int dim = -1;
    S[++dim] = P[0];
    S[++dim] = P[1];
    for (int i = 2; i < n; ++i)
    {
        while (cross(S[dim - 1], S[dim], P[i]) > EPS) --dim;
        S[++dim] = P[i];
    }
    ++dim;
    fout << dim << '\n';
    for (int i = 0 ; i < dim; ++i)
        fout << fixed << setprecision(7) << S[i].x << ' ' << S[i].y << '\n';
    return 0;
}