Pagini recente » Cod sursa (job #373534) | Cod sursa (job #1509133) | Cod sursa (job #2049622) | Cod sursa (job #2700158) | Cod sursa (job #3173705)
#include <bits/stdc++.h>
using namespace std;
struct Point {
double x, y;
bool operator<(Point b) const {
if (x == b.x) return y < b.y;
return x < b.x;
}
bool operator==(Point b) const {
return x == b.x && y == b.y;
}
};
vector<Point> points;
double cross(Point a, Point b, Point o = {0, 0}) {
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
double area(Point a, Point b, Point c) {
return (a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y));
}
bool cmp(Point a, Point b) {
return area(points[0], a, b) < 0;
}
int main() {
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int n;
cin >> n;
points.assign(n, {});
for (int i = 0; i < n; ++i) {
cin >> points[i].x >> points[i].y;
if (points[i] < points[0]) swap(points[i], points[0]);
}
sort(points.begin() + 1, points.end(), cmp);
auto bad = [&](Point a, Point b, Point c) {
return area(a, b, c) > 0;
};
vector<Point> st;
for (int i = 0; i < n; ++i) {
while (st.size() > 1 && bad(st.end()[-2], st.back(), points[i])) st.pop_back();
st.push_back(points[i]);
}
reverse(st.begin(), st.end());
cout << st.size() << endl;
for (Point p : st) cout << fixed << setprecision(13) << p.x << " " << p.y << endl;
}