Cod sursa(job #2988401)

Utilizator rastervcrastervc rastervc Data 4 martie 2023 11:14:13
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.88 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

constexpr double EPSILON = 1e-12;

struct Point {
    double x, y;
    Point() : x(), y() {}
    Point(double x, double y) : x(x), y(y) {}
};

static inline double distance(const Point& A, const Point& B) {
    return (B.x - A.x) * (B.x - A.x) + (B.y - A.y) * (B.y - A.y);
}

static inline int orientation(const Point& A, const Point& B, const Point& C) {
    double d = (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
    if (d <= -EPSILON / 2) return -1;
    if (d >= EPSILON / 2) return 1;
    return 0;
}

static inline vector<Point> convex_hull(vector<Point> polygon) {
    Point P0 = *min_element(
        polygon.begin(), polygon.end(), 
        [](const Point& A, const Point& B) {
            return make_pair(A.y, A.x) < make_pair(B.y, B.x);
        }
    );

    sort(
        polygon.begin(), polygon.end(),
        [&](const Point& A, const Point& B) {
            const int o = orientation(P0, A, B);
            if (o == 0) return distance(P0, A) < distance(P0, B);
            return o > 0;
        }
    );

    vector<Point> hull;
    for (int i = 0; i < polygon.size(); ++i) {
        while (hull.size() > 1 && orientation(hull[hull.size() - 2], hull[hull.size() - 1], polygon[i]) <= 0)
            hull.pop_back();
        hull.push_back(polygon[i]);
    }

    return hull;
}

int main() {
    vector<Point> polygon;
    double x, y;
    int N, i;

    fin >> N;
    for (i = 1; i <= N; ++i) {
        fin >> x >> y;
        polygon.emplace_back(x, y);
    }

    const vector<Point> hull = convex_hull(polygon);

    fout << hull.size() << '\n';
    for (const Point& P : hull)
        fout << P.x << ' ' << P.y << '\n';

    fin.close();
    fout.close();
    return 0;
}