Cod sursa(job #1941863)

Utilizator preda.andreiPreda Andrei preda.andrei Data 27 martie 2017 17:10:23
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.02 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 LeftLower(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 > 0);
}

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

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

        return CounterClockwise(left, a, b);
    };
    sort(vec.begin(), vec.end(), cmp);

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

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

    /* while (!CounterClockwise(hull[hull.size() - 2], hull.back(), hull[0])) {
        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 << fixed << setprecision(12) << p.x << " " << p.y << "\n";
    }

    return 0;
}