Cod sursa(job #1966232)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 15 aprilie 2017 00:15:17
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

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

const int nmax = 120005;
struct pct {
    double x, y;
}v[nmax];
int n, i, j, ind,colt;
int stv[nmax], vf;

bool cmp(const pct &a, const pct &b) {
    return ((a.y-v[1].y)/(a.x-v[1].x)) < ((b.y-v[1].y)/(b.x-v[1].x));
}

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

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

int main() {
    f >> n;
    for (i = 1; i <= n; i++) {
        f >> v[i].x >> v[i].y;
        if (v[i].x < v[colt].x || (v[i].x==v[colt].x &&v[i].y<v[colt].y) || colt == 0)
            colt = i;
    } //g << colt << '\n';
    swap(v[1], v[colt]);
    sort(v+2,v+n+1, cmp);
    stv[1] = 1, stv[2] = 2, vf = 2;
    for (i = 3; i <= n; i++) {
        while (vf > 2 && convex(v[stv[vf-1]], v[stv[vf]], v[i] )== 0) vf--;
        stv[++vf] = i;
    }
    g << vf << '\n';
    for (i = 1; i <= vf; i++)
        g << fixed << setprecision(6) << v[stv[i]].x << ' ' << v[stv[i]].y << '\n';

    return 0;
}