Cod sursa(job #2753474)

Utilizator preda.andreiPreda Andrei preda.andrei Data 22 mai 2021 23:22:44
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <vector>

using namespace std;

using Point = pair<long double, long double>;

bool CounterClockwise(const Point& a, const Point& b, const Point& c) {
    auto area = a.first * b.second + b.first * c.second + a.second * c.first
              - b.second * c.first - a.first * c.second - a.second * b.first;

    return area > 0;
}

bool operator<(const Point& a, const Point& b) {
    static constexpr long double kEps = 1e-12;

    if (abs(a.first - b.first) > kEps) {
        return a.first < b.first;
    }
    return a.second < b.second;
}

vector<Point> ConvexHull(vector<Point>& points) {
    auto start = *min_element(points.begin(), points.end());

    sort(points.begin(), points.end(), [start](const Point& a, const Point& b) {
        if (a == start || b == start) {
            return a == start;
        }
        return CounterClockwise(start, a, b);
    });

    vector<Point> hull = {points[0], points[1]};
    for (size_t i = 2; i < points.size(); i += 1) {
        while (hull.size() > 2) {
            auto a = hull[hull.size() - 2];
            auto b = hull[hull.size() - 1];
            if (CounterClockwise(a, b, points[i])) {
                break;
            }
            hull.pop_back();
        }
        hull.push_back(points[i]);
    }
    return hull;
}

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

    int n;
    fin >> n;

    vector<Point> points(n);
    for (auto& p : points) {
        fin >> p.first >> p.second;
    }

    auto hull = ConvexHull(points);
    fout << hull.size() << "\n";

    fout << fixed << setprecision(12);
    for (const auto& p : hull) {
        fout << p.first << " " << p.second << "\n";
    }
    return 0;
}