Pagini recente » Cod sursa (job #2506128) | Cod sursa (job #45988) | Cod sursa (job #607452) | Cod sursa (job #761826) | Cod sursa (job #3173702)
#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 dist(Point a, Point b) {
double dx = a.x - b.x, dy = a.y - b.y;
return dx * dx + dy * dy;
}
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);
}
bool up(Point p) {
return p.y > 0 || (p.y == 0 && p.x >= 0);
}
bool cmp(Point a, Point b) {
Point o = points[0];
if (up(a) != up(b)) return up(a) < up(b);
if (cross(a, b, o) == 0) return dist(o, a) < dist(o, b);
return cross(a, b, o) < 0;
}
bool cmp2(Point b, Point c) {
Point a = points[0];
return (a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y)) < 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 cross(b, c, a) >= 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;
}