Cod sursa(job #1941726)

Utilizator preda.andreiPreda Andrei preda.andrei Data 27 martie 2017 15:59:10
Problema Infasuratoare convexa Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 2.42 kb
#include <cmath>
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <vector>

using namespace std;

const double kEps = 1e-12;
const double kInf = 1e10;

struct Point
{
    double x, y;

    bool operator==(const Point &a) const {
        return (x == a.x) && (y == a.y);
    }
};

Point RightLower(const Point &a, const Point &b)
{
    if (a.x - b.x > kEps) {
        return a;
    }
    if (a.x - b.x < kEps) {
        return b;
    }
    return (a.y - b.y < kEps) ? a : b;
}

bool CounterClockwise(const Point &a, const Point &b, const Point &c)
{
    double res = a.x * (b.y - c.y) + a.y * (c.x - b.x) + b.x * c.y - b.y * c.x;
    return (res > kEps);
}

vector<Point> ConvexHull(vector<Point> &vec)
{
    Point right = {-kInf, kInf};
    for (const auto &p : vec) {
        right = RightLower(right, p);
    }

    auto cmp = [right](const Point &a, const Point &b) -> bool {
        if (a == right) {
            return true;
        }
        if (b == right) {
            return false;
        }

        if (a.y - right.y > kEps && right.y - b.y > kEps) {
            return true;
        }
        if (b.y - right.y > kEps && right.y - a.y > kEps) {
            return false;
        }

        double dx_a = abs(a.x - right.x);
        double dy_a = abs(a.y - right.y);

        double dx_b = abs(b.x - right.x);
        double dy_b = abs(b.y - right.y);

        if (a.y - right.y > kEps) {
            return dx_a * dy_b - dx_b * dy_a < kEps;
        }
        return dx_a * dy_b - dx_b * dy_a > kEps;
    };
    sort(vec.begin(), vec.end(), cmp);
    vec.push_back(right);

    vector<Point> hull(3);
    hull[0] = vec[0];
    hull[1] = vec[1];
    hull[2] = vec[2];

    for (unsigned i = 3; i < vec.size(); ++i) {
        while (!CounterClockwise(hull[hull.size() - 2], hull.back(), vec[i])) {
            hull.pop_back();
        }
        hull.push_back(vec[i]);
    }
    hull.pop_back();
    return hull;
}

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

    int n;
    fin >> n;

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

    auto hull = ConvexHull(points);
    fout << hull.size() << "\n";
    for (const auto &p : hull) {
        fout << setprecision(12) << p.x << " " << p.y << "\n";
    }

    return 0;
}