Cod sursa(job #1913805)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 8 martie 2017 14:06:29
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

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

const double f_mare = 1e9+6;

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

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

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

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

int main() {
    f >> n;
    colt.x = colt.y = f_mare;
    ind = 1;
    for (i = 1; i <= n; i++) {
        f >> v[i].x >> v[i].y;
        if (v[ind].x > v[i].x || (v[ind].x == v[i].x && v[i].y < v[ind].y))
            ind = i;
    }
   // g <<  colt.x << ' ' << colt.y << '\n';
    //g << ind << ' ';
    swap(v[1], v[ind]);
    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[vf=2] = 2, stiva[1] = 1;
    for (i = 3; i <= n; i++) {
        while (vf > 2 && convex( 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';
    return 0;
}