Pagini recente » Cod sursa (job #3221062) | Cod sursa (job #300264) | Cod sursa (job #1084622) | Cod sursa (job #3135360)
#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;
}
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 : points) {
fout << point << '\n';
}
fout.close();
return 0;
}