Pagini recente » Cod sursa (job #2615924) | Cod sursa (job #360480) | Cod sursa (job #434887) | Cod sursa (job #1019461) | Cod sursa (job #3135356)
#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;
}