Cod sursa(job #2664840)

Utilizator gavra_bogdanBogdan Gavra gavra_bogdan Data 29 octombrie 2020 15:54:34
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
#define ld double
#define pd std::pair<ld, ld>
#define x first
#define y second

const int nmax = 12e4 + 5;
const ld eps = 1e-12;
std::vector<int>hull = { 0, 1 };
bool f[nmax];

bool cross(pd a, pd b, pd c) {
    return (c.y * (b.x - a.x) - c.x * (b.y - a.y) + b.y * a.x - b.x * a.y < eps);
}

int main() {
    std::ifstream fin("infasuratoare.in");
    std::ofstream fout("infasuratoare.out");
    int n, dir = 1;
    fin >> n;
    std::vector<pd>v(n);
    for (int i = 0; i < n; i++) fin >> v[i].y >> v[i].x;
    std::sort(v.begin(), v.end());
    f[1] = 1;
    for (int i = 2; i!=-1; i += dir) 
        if(!f[i]){
            while (hull.size() > 1 and !cross(v[hull[hull.size() - 2]], v[hull.back()], v[i]))
                f[hull.back()] = 0, hull.pop_back();
            hull.push_back(i), f[hull.back()] = 1;
            if (hull.back() == n - 1) dir = -1;
        }
    hull.pop_back();
    fout << hull.size() << "\n";
    for (int z:hull) fout << std::fixed << std::setprecision(12) << v[z].y << " " << v[z].x << "\n";
}