Cod sursa(job #3357793)

Utilizator TestLicenta123Test Test TestLicenta123 Data 13 iunie 2026 14:57:28
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.09 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <climits>
#include <iomanip>

struct Point {
    double x = 0, y = 0;

    Point() = default;
    Point(double x, double y) : x(x), y(y) {}

    inline friend std::istream &operator>>(std::istream &is, Point &p) {
        return is >> p.x >> p.y;
    }

    inline friend std::ostream &operator<<(std::ostream &os, const Point &p) {
        return os << p.x << " " << p.y;
    }

    static double cross_product(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() {
    std::ifstream input("infasuratoare.in");
    std::ofstream output("infasuratoare.out");

    int n;
    input >> n;
    std::vector<Point> points(n);
    Point ref(INT_MAX, INT_MAX);
    int pos = 0;

    for (int i = 0; i < n; ++i) {
        input >> points[i];
        if (points[i].x < ref.x || (points[i].x == ref.x && points[i].y < ref.y)) {
            ref = points[i];
            pos = i;
        }
    }

    std::swap(points[0], points[pos]);

    auto cmp = [ref](const Point &a, const Point &b) {
        double cp = Point::cross_product(ref, a, b);
        if (cp == 0) {
            double da = (a.x - ref.x) * (a.x - ref.x) + (a.y - ref.y) * (a.y - ref.y);
            double db = (b.x - ref.x) * (b.x - ref.x) + (b.y - ref.y) * (b.y - ref.y);
            return da < db;
        }
        return cp > 0;
    };

    std::sort(points.begin() + 1, points.end(), cmp);

    std::vector<Point> hull;
    hull.push_back(points[0]);

    for (int i = 1; i < n; ++i) {
        while (hull.size() >= 2) {
            Point &a = hull[hull.size() - 2];
            Point &b = hull[hull.size() - 1];
            Point &c = points[i];
            if (Point::cross_product(a, b, c) <= 0) {
                hull.pop_back();
            } else break;
        }
        hull.push_back(points[i]);
    }

    output << hull.size() << "\n";
    output << std::setprecision(12) << std::fixed;
    for (const auto &p : hull) {
        output << p << "\n";
    }

    return 0;
}