Cod sursa(job #2543439)

Utilizator catalintermureTermure Catalin catalintermure Data 11 februarie 2020 10:04:13
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

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

struct Punct {
    double x, y;

    bool operator<(const Punct& other) const {
        return x < other.x || (x == other.x && y < other.y);
    }
};

const int NMAX = 120000;

Punct v[NMAX];
Punct hull[NMAX];

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

int main() {
    int n, hlen = 0;
    inf >> n;
    for(int i = 0; i < n; i++) {
        inf >> v[i].x >> v[i].y;
    }
    sort(v, v + n);
    for(int i = 0; i < n; i++) {
        while(hlen > 1 && det(hull[hlen - 2], hull[hlen - 1], v[i]) < 0) {
            hlen--;
        }
        hull[hlen++] = v[i];
    }
    for(int i = n - 2; i >= 0; i--) {
        while(hlen > 1 && det(hull[hlen - 2], hull[hlen - 1], v[i]) < 0) {
            hlen--;
        }
        hull[hlen++] = v[i];
    }

    hlen--;
    outf << hlen << '\n';
    outf << setprecision(6) << fixed;
    for(int i = 0; i < hlen; i++) {
        outf << hull[i].x << ' ' << hull[i].y << '\n';
    }
    return 0;
}