Cod sursa(job #3135356)

Utilizator pregoliStana Andrei pregoli Data 2 iunie 2023 22:24:35
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <bits/stdc++.h>
using namespace std;
const string FNAME = "infasuratoare";
ifstream fin(FNAME + ".in");
ofstream fout(FNAME + ".out");
constexpr int PREC = 6;
using Point = pair<double, double>;
#define x first
#define y second

istream& operator>>(istream &in, Point &point) {
    in >> point.x >> point.y;
    return in;
}

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

vector<Point> readPoints() {
    int n;
    fin >> n;
    vector<Point> points(n);
    for (auto &point : points) {
        fin >> point;
    }
    return points;
}

int crossProd(const Point &p, const Point &q, const Point &r) {
    return q.x*r.y + p.x*q.y + r.x*p.y - q.x*p.y - r.x*q.y - p.x*r.y;
}

Point getNextAfterTop(stack<Point> &st) {
    Point top = st.top();
    st.pop();
    Point nextAfterTop = st.top();
    st.push(top);
    return nextAfterTop;
}

int main() {
    vector<Point> points = readPoints();
    vector<Point>::iterator minIt = min_element(points.begin(), points.end(), [](const Point &p1, const Point &p2)->bool {
        return (p1.y < p2.y || (p1.y == p2.y && p1.x > p2.x));
    });
    iter_swap(points.begin(), minIt);
    sort(points.begin() + 1, points.end(), [=](const Point &p1, const Point &p2)->bool {
        return crossProd(points[0], p1, p2) > 0;
    });
    stack<Point> ans;
    ans.push(points[0]);
    ans.push(points[1]);
    for (size_t i = 2; i < points.size(); i++) {
        while (ans.size() >= 2 && crossProd(getNextAfterTop(ans), ans.top(), points[i]) < 0) {
            ans.pop();
        }
        ans.push(points[i]);
    }
    fout << ans.size() << '\n' << fixed << setprecision(PREC);
    for (; !ans.empty(); ans.pop()) {
        fout << ans.top() << '\n';
    }
    fout.close();
    return 0;
}