Cod sursa(job #3318090)

Utilizator burcuriciBucur Stefan burcurici Data 27 octombrie 2025 01:40:26
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>
using namespace std;

struct Point {
    double x, y;
    bool operator<(const Point &other) const {
        if (x == other.x) return y < other.y;
        return x < other.x;
    }
};

double cross(const Point &A, const Point &B, const Point &C) {
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}

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

    int N;
    fin >> N;
    vector<Point> pts(N);
    for (int i = 0; i < N; i++) {
        fin >> pts[i].x >> pts[i].y;
    }

    sort(pts.begin(), pts.end());

    vector<Point> hull;


    for (int i = 0; i < N; i++) {
        while (hull.size() >= 2 && cross(hull[hull.size()-2], hull.back(), pts[i]) <= 0) {
            hull.pop_back();
        }
        hull.push_back(pts[i]);
    }


    size_t lower_size = hull.size();
    for (int i = N - 2; i >= 0; i--) {
        while (hull.size() > lower_size && cross(hull[hull.size()-2], hull.back(), pts[i]) <= 0) {
            hull.pop_back();
        }
        hull.push_back(pts[i]);
        if (i == 0) break;
    }

    hull.pop_back();

    fout << hull.size() << "\n";
    fout << fixed << setprecision(6);
    for (auto &p : hull) {
        fout << p.x << " " << p.y << "\n";
    }

    return 0;
}