Cod sursa(job #1947923)

Utilizator preda.andreiPreda Andrei preda.andrei Data 31 martie 2017 15:19:48
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.95 kb
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <vector>

using namespace std;

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

struct Point { double x, y; };

inline double Abs(double a) { return a < 0 ? -a : a; }
inline bool Smaller(double a, double b) { return a - b < kEps; }
inline bool Equal(double a, double b) { return Abs(a - b) < kEps; }

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

inline bool CounterClock(const Point &a, const Point &b, const Point &c)
{
    double delta = a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
    return delta > 0;
}

vector<Point> FindHull(vector<Point> &vec)
{
    Point left = {kInf, kInf};
    for (const auto &p : vec) {
        if (Smaller(p.x, left.x) ||
                (Equal(p.x, left.x) && Smaller(p.y, left.y))) {
            left = p;
        }
    }

    auto cmp = [left](const Point &a, const Point &b) -> bool {
        if (a == left){
            return true;
        } else if (b == left) {
            return false;
        }
        return CounterClock(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 &&
                !CounterClock(hull[hull.size() - 2], hull.back(), vec[i])) {
            hull.pop_back();
        }
        hull.push_back(vec[i]);
    }
    return hull;
}

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

    int n;
    fin >> n;

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

    auto hull = FindHull(vec);
    fout << hull.size() << "\n";

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

    return 0;
}