Cod sursa(job #2542600)

Utilizator catalintermureTermure Catalin catalintermure Data 10 februarie 2020 11:50:07
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <fstream>
#include <algorithm>
#include <iostream>
#include <iomanip>

using namespace std;

const double EPS = 1e-12;

ifstream inf("infasuratoare.in");
ofstream outf("infasuratoare.out");

const int NMAX = 120000;

struct Point {
    double x, y;
};

Point v[NMAX];
int infas[NMAX];
bool viz[NMAX];

double cross_product(Point o, Point a, Point b) { /// AOB in sens trigonometric de la A la B
    return ((a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x));
}

int main() {
    int n;
    inf >> n;
    for(int i = 0; i < n; i++) {
        inf >> v[i].x >> v[i].y;
    }
    sort(v, v + n, [](Point a, Point b) {
            return a.x < b.x || (a.x == b.x && a.y < b.y);
         });

    int infaslen = 0;
    for(int i = 0; i < n; i++) {
        while(infaslen >= 1 && cross_product(v[infas[infaslen - 2]], v[infas[infaslen - 1]], v[i]) < EPS) {
            viz[infas[--infaslen]] = false;
        }
        viz[i] = true;
        infas[infaslen++] = i;
    }
    for(int i = n - 2; i; i--) {
        if(viz[i]) {
            continue;
        }
        while(infaslen >= 1 && cross_product(v[infas[infaslen - 2]], v[infas[infaslen - 1]], v[i]) < EPS) {
            viz[infas[--infaslen]] = false;
        }
        viz[i] = true;
        infas[infaslen++] = i;
    }
    outf << infaslen << '\n';
    outf << setprecision(6) << fixed;
    for(int i = 0; i < infaslen; i++) {
        outf << v[infas[i]].x << ' ' << v[infas[i]].y << '\n';
    }
    return 0;
}