Cod sursa(job #1857984)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 26 ianuarie 2017 21:57:56
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>

using namespace std;

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

struct punct {
    double x, y, panta;
};
punct v[120005],colt;
int pc;
int n, i;
int stiva[120005], vf;

bool cmp(punct a, punct b) {
    return a.panta < b.panta;
}

bool convex(punct a, punct b, punct c) {
    double det = (1LL*a.x*b.y+1LL*b.x*c.y+1LL*a.y*c.x-1LL*c.x*b.y-1LL*a.x*c.y-1LL*b.x*a.y);
    return det > 0;
}

int main() {
    f >> n;
    colt.x=colt.y=2e9;
    for (i = 1; i <= n; i++) {
        f >> v[i].x >> v[i].y;
        if (colt.x > v[i].x || (colt.x ==v[i].x && v[i].y < colt.y))
            colt = v[i], pc= i;
    }
    swap(v[1], v[pc]);
    for (i = 2; i <= n; i++)
        v[i].panta = (v[i].y-v[1].y)/(v[i].x-v[1].x);
    sort(v+2, v+n+1, cmp);
    stiva[1] = 1, stiva[2] = 2, vf = 2;
    for (i = 3; i <= n; i++) {
        if (convex(v[stiva[vf-1]], v[stiva[vf]], v[i])==0 && vf > 2)
            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';

    return 0;
}