Cod sursa(job #2754630)

Utilizator NanuGrancea Alexandru Nanu Data 26 mai 2021 10:12:29
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

#define DIM 120005

int n, st[DIM], i, vf, semn;
bool sel[DIM];
struct nanu {
    double x, y;
} v[DIM];

static inline bool cmp(nanu a, nanu b) {
    return (a.y < b.y || (a.y == b.y && a.x < b.x));
}

static inline int det(double x1, double Y1, double x2, double y2, double x3, double y3) {
    int d = (x2 - x1) * (y3 - Y1) - (x3 - x1) * (y2 - Y1);
    if(d < 0)
        return - 1;
    return 1;
}

int main() {
    cin >> n;
    for(i = 1; i <= n; i++)
        cin >> v[i].x >> v[i].y;
    sort(v + 1, v + n + 1, cmp);

    st[++vf] = 1;
    st[++vf] = 2;
    sel[2] = 1;

    i = 3, semn = 1;
    while(sel[1] == 0) {
        while(sel[i]) {
            if(i == n)
                semn = -1;
            i += semn;
        }
        while(vf >= 2 && det(v[st[vf - 1]].x, v[st[vf - 1]].y, v[st[vf]].x, v[st[vf]].y, v[i].x, v[i].y) == -1)
            sel[st[vf--]] = 0;
        st[++vf] = i;
        sel[i] = 1;
    }

    cout << vf - 1 << '\n';
    for(i = 1; i < vf; i++)
        cout << fixed << setprecision(6) << v[st[i]].x << " " << v[st[i]].y << '\n';

    return 0;
}