Cod sursa(job #3301079)

Utilizator VramzVramita Darius Adrian Vramz Data 21 iunie 2025 14:45:22
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>
using namespace std;

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

struct P {
    long double x, y;
} a[150005];

int n, stk[150005], top, ref;
long double bx, by = 1e18;

bool cmp(const P &p1, const P &p2) {
    return p1.x * p2.y >= p2.x * p1.y;
}

bool ok(P p1, P p2, P p3) {
    long double d = p1.x * (p2.y - p3.y) + p2.x * (p3.y - p1.y) + p3.x * (p1.y - p2.y);
    return d > 0;
}

int main() {
    fin >> n;
    for (int i = 1; i <= n; i++) {
        fin >> a[i].x >> a[i].y;
        if (a[i].y < by || (a[i].y == by && a[i].x < bx)) {
            bx = a[i].x;
            by = a[i].y;
            ref = i;
        }
    }

    for (int i = 1; i <= n; i++) {
        a[i].x -= bx;
        a[i].y -= by;
    }

    swap(a[1], a[ref]);
    sort(a + 2, a + n + 1, cmp);

    stk[1] = 1;
    stk[2] = 2;
    top = 2;

    for (int i = 3; i <= n; i++) {
        while (top >= 2 && !ok(a[stk[top - 1]], a[stk[top]], a[i])) top--;
        stk[++top] = i;
    }

    fout << top << '\n';
    fout << fixed << setprecision(10);
    for (int i = 1; i <= top; i++) {
        fout << a[stk[i]].x + bx << ' ' << a[stk[i]].y + by << '\n';
    }

    return 0;
}