Cod sursa(job #3135361)

Utilizator pregoliStana Andrei pregoli Data 2 iunie 2023 22:57:33
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 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;
}

double 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;
}

int main() {
    vector<Point> points = readPoints();
    points.shrink_to_fit();
    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);
    });
    vector<Point> ans = { points[0], points[1] };
    for (size_t i = 2; i < points.size(); i++) {
        while (ans.size() >= 2 && crossProd(ans[ans.size() - 2], ans.back(), points[i]) < 0) {
            ans.pop_back();
        }
        ans.push_back(points[i]);
    }

    fout << ans.size() << '\n';
    fout << fixed << setprecision(PREC);
    for (const auto &point : ans) {
        fout << point << '\n';
    }
    fout.close();
    return 0;
}