Cod sursa(job #3301090)

Utilizator anamaria-carina.orszariAnamaria-Carina Orszari anamaria-carina.orszari Data 21 iunie 2025 16:19:02
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <algorithm>
#include <iomanip>
#include <fstream>
using namespace std;

const int N = 120005;
const double EPS = 0.000000000001;

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

struct Pt {
    double x, y;
};

int n;
Pt p[N];
bool inHull[N];
int hull[N], top;

bool cmp(const Pt& a, const Pt& b) {
    if (a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}

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

double cross(const Pt& o, const Pt& a, const Pt& b) {
    return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y);
}

void solve() {
    sort(p + 1, p + n + 1, cmp);

    hull[1] = 1;
    hull[2] = 2;
    top = 2;
    inHull[2] = true;

    int dir = 1;
    for (int i = 1; i > 0; i += dir) {
        if (inHull[i]) continue;
        while (top >= 2 && cross(p[hull[top - 1]], p[hull[top]], p[i]) < EPS)
            inHull[hull[top--]] = false;
        hull[++top] = i;
        inHull[i] = true;

        if (i == n)
            dir = -1;
    }

    fout << top - 1 << "\n";
    fout << fixed << setprecision(6);
    for (int i = 1; i < top; ++i)
        fout << p[hull[i]].x << " " << p[hull[i]].y << "\n";
}

int main() {
    read();
    solve();
}