Cod sursa(job #2172094)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 15 martie 2018 15:00:33
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

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

const int N = 120005;
struct punct {
    double x, y;
};
punct v[N], minim;
int n, i, j,ind;
int stiva[N], vf;

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);
}

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

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

    stiva[1] = 1, stiva[vf=2] = 2;
    for (i = 3; i <= n; i++) {
        while (vf >= 2 && det(v[ stiva[vf-1] ], v[ stiva[vf] ], v[i]) <= 0) 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';
}