Cod sursa(job #3295773)

Utilizator alexdumitruAlexandru Dumitru alexdumitru Data 8 mai 2025 13:28:32
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>

std::ifstream fin("infasuratoare.in");
std::ofstream fout("infasuratoare.out");

const int MAX_N = 120000;

int n;

struct Point {
    double x, y;
} a[MAX_N + 1];

bool in[MAX_N + 1];

int stk[MAX_N + 1], sz;

double det(Point p1, Point p2, Point p3) {
    return p1.x * p2.y + p2.x * p3.y + p3.x * p1.y
         - p2.y * p3.x - p3.y * p1.x - p1.y * p2.x;
}

void solve() {
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> a[i].x >> a[i].y;

    std::sort(a + 1, a + n + 1, [](const Point & a, const Point & b) {
        if (a.x != b.x)
            return a.x < b.x;
        return a.y < b.y;
    });

    stk[++sz] = 1;
    stk[++sz] = 2;
    in[2] = true;

    for (int i = 3; i <= n; i++) {
        while (sz >= 2 && det(a[i], a[stk[sz - 1]], a[stk[sz]]) >= 0) {
            in[stk[sz]] = false;
            sz--;
        }
        stk[++sz] = i;
        in[i] = true;
    }

    for (int i = n; i >= 1; i--) {
        if (in[i]) continue;

        while (sz >= 2 && det(a[i], a[stk[sz - 1]], a[stk[sz]]) >= 0) {
            in[stk[sz]] = false;
            sz--;
        }
        stk[++sz] = i;
        in[i] = true;
    }

    sz--;

    fout << sz << '\n';

    fout << std::fixed << std::setprecision(12);

    for (int i = 1; i <= sz; i++) {
        fout << a[stk[i]].x << ' ' << a[stk[i]].y << '\n';
    }
}

int main() {
    solve();
    return 0;
}