Cod sursa(job #2084261)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 8 decembrie 2017 20:55:29
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

const int nmax = 120005;
struct punct {
    double x, y;
}v[nmax], pmin;

const double EPS = 1e-12;
int n, i, j, poz;
int stiva[nmax], vf;

bool cmp(punct a, punct b) {
    return (b.y-pmin.y)*(a.x-pmin.x) > (a.y-pmin.y)*(b.x-pmin.x);
}

double det(punct a, punct b, punct c) {
    return a.x*b.y+b.x*c.y+c.x*a.y - c.x*b.y-b.x*a.y-a.x*c.y;
}

bool convex(punct a, punct b, punct c) {
    return (det(a, b, c) > EPS);
}

int main() {
    f >> n;
    pmin.x = pmin.y = 2e9;
    for (i = 1; i <= n; i++) {
        f >> v[i].x >> v[i].y;
        if (v[i].x < pmin.x || (v[i].x == pmin.x && v[i].y < pmin.y))
            pmin = v[i], poz = i;
    }
    swap(v[1], v[poz]);
    sort(v+2, v+n+1, cmp);

    stiva[1] = 1, stiva[2] = 2;
    vf = 2;
    for (i = 3; i <= n; i++) {
        while (convex(v[stiva[vf-1]],v[stiva[vf]],v[i]) == 0 && vf > 1)
            vf--;
        stiva[++vf] = i;
    }
    g << vf << '\n';
    for (i = 1; i <= vf; i++)
        g << fixed << setprecision(6) << v[stiva[i]].x << ' ' << v[stiva[i]].y << '\n';

}