Cod sursa(job #3284356)

Utilizator BuruianaRaresAndreiBuruiana Rares Andrei BuruianaRaresAndrei Data 11 martie 2025 15:07:32
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>

using namespace std;

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

struct Point {
    double x, y;
};

int n;
Point v[120005];

Point stck[120005];
int head;

double cross_product(Point a, Point b, Point c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

bool cmp(Point a, Point b) {
    return cross_product(v[1], a, b) < 0;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); in.tie(nullptr);

    // input
    in >> n;
    for(int i = 1; i <= n; i++) {
        in >> v[i].x >> v[i].y;
    }

    // sort
    int pos = 1;
    for(int i = 2; i <= n; i++) {
        if(v[i].x < v[pos].x || (v[i].x == v[pos].x && v[i].y < v[pos].y)) {
            pos = i;
        }
    }
    swap(v[1], v[pos]);
    sort(v + 2, v + n + 1, cmp);

    // convex hull
    stck[1] = v[1];
    stck[2] = v[2];
    head = 2;
    for(int i = 3; i <= n; i++) {
        while(head >= 2 && cross_product(stck[head - 1], stck[head], v[i]) > 0) {
            head--;
        }
        stck[++head] = v[i];
    }

    // output
    out << head << '\n';
    for(int i = head; i >= 1; i--) {
        out << fixed << setprecision(9) << stck[i].x << ' ' << stck[i].y << '\n';
    }

    return 0;
}