Cod sursa(job #2132205)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 15 februarie 2018 16:17:49
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>

using namespace std;

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

const int nmax = 120005, f_mare = 1e9;
int n, i, poz;
struct punct {
    double x, y;
} a[nmax], minim;
int stiva[nmax], vf;

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 - c.y*a.x;
}

bool cmp(const punct &a, const punct &b) {
    return (a.y-minim.y)*(b.x-minim.x) < (b.y-minim.y)*(a.x-minim.x);
}

int main() {
    f >> n;
    minim = {f_mare, f_mare};
    for (i = 1; i <= n; i++) {
        f >> a[i].x >> a[i].y;
        if (a[i].x < minim.x || (a[i].x == minim.x && a[i].y < minim.y))
            poz = i, minim = a[i];
    }
    swap(a[1], a[poz]);
    sort(a+2,a+n+1,cmp);
    stiva[1] = 1, stiva[2] = 2;
    vf = 2;
    for (i = 3; i <= n; i++) {
        while (vf > 2 && det(a[stiva[vf-1]], a[stiva[vf]], a[i]) <= 0) vf--;
        stiva[++vf] = i;
    }
    g << vf << '\n';
    for (i = 1; i <= vf; i++)
        g << fixed << setprecision(6) << a[stiva[i]].x << ' ' << a[stiva[i]].y << '\n';
    return 0;
}