Cod sursa(job #3138944)

Utilizator pregoliStana Andrei pregoli Data 23 iunie 2023 15:21:44
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.85 kb
#include <bits/stdc++.h>
using namespace std;
const string FNAME = "infasuratoare";
ifstream fin(FNAME + ".in");
ofstream fout(FNAME + ".out");
constexpr int PREC = 12;

struct Point {
    double x, y;
    Point() { x = y = 0; }
    Point(double x, double y): x(x), y(y) {}
    static double crossProd(const Point &a, const Point &b) {
        return a.x * b.y - a.y * b.x;
    }
    static double crossProd(const Point &a, const Point &b, const Point &c) {
        return crossProd(b - a, c - a);
    }
    bool operator <(const Point &other) const noexcept {
        return (y < other.y || (y == other.y && x < other.x));
    }
    bool operator ==(const Point &other) const noexcept {
        return x == other.x && y == other.y;
    }
    Point operator -(const Point &other) const noexcept {
        return Point(x - other.x, y - other.y);
    }
    Point &operator =(const Point &other) {
        this->x = other.x;
        this->y = other.y;
        return *this;
    }

    friend istream &operator >>(istream &in, Point &point) {
        in >> point.x >> point.y;
        return in;
    }
    friend ostream &operator << (ostream &out, const Point &point) {
        out << point.x << ' ' << point.y;
        return out;
    }
};

class GrahamScanner {
public:
    GrahamScanner(const vector<Point> &points): points(points) {
        init();
    }

    vector<Point> scan() {
        vector<Point> ans = { points[0], points[1] };
        for (size_t i = 2; i < points.size(); i++) {
            while (ans.size() >= 2 && Point::crossProd(ans[ans.size() - 2], ans.back(), points[i]) < 0) {
                ans.pop_back();
            }
            ans.push_back(points[i]);
        }
        return ans;
    }

private:
    vector<Point> points;

    void init() {
        placeSentinel();
        sort(points.begin() + 1, points.end(), GrahamScanner::PolarCmp(points[0]));
    }

    void placeSentinel() {
        vector<Point>::iterator sentinel = points.end();
        for (auto it = points.begin(); it != points.end(); it++) {
            if (*it < *sentinel) {
                sentinel = it;
            }
        }
        iter_swap(points.begin(), sentinel);
    }

    struct PolarCmp {
        Point origin;
        PolarCmp(const Point &origin): origin(origin) {}

        bool operator ()(const Point &a, const Point &b) {
            return Point::crossProd(origin, a, b) > 0;
        }
    };
};

int main() {
    int n;
    fin >> n;
    vector<Point> points(n);
    points.shrink_to_fit();
    for (auto &point : points) {
        fin >> point;
    }

    GrahamScanner gScanner(points);
    auto hull = gScanner.scan();
    fout << hull.size() << '\n';
    for (const auto &point : hull) {
        fout << fixed << setprecision(PREC) << point << '\n';
    }
    fout.close();
    return 0;
}