Cod sursa(job #3301080)

Utilizator VramzVramita Darius Adrian Vramz Data 21 iunie 2025 14:46:38
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;

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

int n, st[150005], top, pmin;
long double bx, by = 1e18;

long double cross(P a, P b, P c) {
    return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
}

bool cmp(P a, P b) {
    return a.x * b.y >= b.x * a.y;
}

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

    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;
            pmin = i;
        }
    }

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

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

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

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

    return 0;
}