Cod sursa(job #2570741)

Utilizator stefan_creastaStefan Creasta stefan_creasta Data 4 martie 2020 18:56:16
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.68 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 = atan2(first.y - init.y, first.x - init.x);
    double p2 = atan2(second.y - init.y, second.x - init.x);
    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;
        }
    }
    Punct aux = v[1];
    v[1] = v[poz];
    v[poz] = aux;
    sort(v + 2, v + n + 1, cmp);
    v[n + 1] = v[n];
    st[1] = 1;
    st[2] = 2;
    int top = 2;
    for(int i = 3; i <= n + 1; 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 << " " << fixed << setprecision(6) << v[st[i]].y << "\n";
    }
    out << "\n";
    return 0;
}