Cod sursa(job #2462850)

Utilizator preda.andreiPreda Andrei preda.andrei Data 27 septembrie 2019 21:45:41
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.85 kb
#include <algorithm>
#include <cmath>
#include <fstream>
#include <iomanip>
#include <vector>

using namespace std;

using Point = pair<double, double>;

constexpr double kEps = 1e-13;

bool operator<(const Point &a, const Point &b)
{
    if (abs(a.first - b.first) < kEps) {
        return a.second < b.second;
    }
    return a.first < b.first;
}

bool CounterClockwise(const Point &a, const Point &b, const Point &c)
{
    return a.first * b.second + a.second * c.first + b.first * c.second
        - b.second * c.first - a.first * c.second - a.second * b.first > 0;
}

Point MinPoint(const vector<Point> &points)
{
    return *min_element(points.begin(), points.end());
}

vector<Point> ConvexHull(vector<Point> &points)
{
    auto start = MinPoint(points);
    auto cmp = [start] (const Point &a, const Point &b) {
        if (a == start) {
            return true;
        } else if (b == start) {
            return false;
        }
        return CounterClockwise(start, a, b);
    };

    sort(points.begin(), points.end(), cmp);

    vector<Point> hull = {points[0], points[1]};
    for (size_t i = 2; i < points.size(); i += 1) {
        while (hull.size() > 1) {
            auto prev1 = hull[hull.size() - 1];
            auto prev2 = hull[hull.size() - 2];

            if (CounterClockwise(prev2, prev1, 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";

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

    return 0;
}