Cod sursa(job #2570810)

Utilizator stefan_creastaStefan Creasta stefan_creasta Data 4 martie 2020 19:29:01
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.72 kb
#include <cmath>
#include <iomanip>
#include <fstream>
#include <algorithm>
using namespace std;
const int NMAX = 120005;
const double EPS = 1e-8;
const double INF = 1000000000;
ifstream in ("infasuratoare.in");
ofstream out ("infasuratoare.out");
struct Punct {
    double x, y;
};
Punct v[NMAX];
Punct init;
bool cmp(Punct first, Punct second) {
    double p1 = (first.y - init.y) / (first.x - init.x);
    double p2 = (second.y - init.y) /  (second.x - init.x);
    if(p1 <= -EPS && p2 <= -EPS) {
        return p1 < p2;
    }
    if(p1 >= EPS && p2 >= EPS) {
        return p1 < p2;
    }
    return p1 > p2;
}
double aflare_arie(Punct a, Punct b, Punct c) {
    return ((a.x - b.x) * (a.y - c.y) - (a.y - b.y) * (a.x - c.x)) / 2;
}
bool e_det(Punct a, Punct b, Punct c) {
    double arie = aflare_arie(a, b, c);
    if(arie >= EPS) {
        return 1;
    }
    return 0;
}
int st[NMAX];

int main() {
    int n;
    in >> n;
    init = {INF, INF};
    int poz = 1;
    for(int i = 1; i <= n; i++) {
        in >> v[i].x >> v[i].y;
        if(init.y > v[i].y) {
            init = v[i];
            poz = i;
        }
        else if(init.x > v[i].x && init.y == v[i].y) {
            init = v[i];
            poz = i;
        }
    }
    swap(v[1], v[poz]);
    sort(v + 2, v + n + 1, cmp);
    st[1] = 1;
    st[2] = 2;
    int top = 2;
    for(int i = 3; i <= n; i++) {
        while(top > 1 && e_det(v[st[top - 1]], v[st[top]], v[i]) == 0) {
            top--;
        }
        st[++top] = i;
    }
    out << top << "\n";
    for(int i = 1; i <= top; i++) {
        out << fixed << setprecision(6) << v[st[i]].x << " " << v[st[i]].y << "\n";
    }
    out << "\n";
    return 0;
}