Pagini recente » Cod sursa (job #2703675) | Cod sursa (job #3129253) | Cod sursa (job #624832) | Cod sursa (job #926048) | Cod sursa (job #3301015)
#include <bits/stdc++.h>
using namespace std;
#define precizie 1e-12
struct Point {
double x, y;
};
bool comp(const Point& A, const Point& B) {
if (fabs(A.x - B.x) < precizie)
return A.x < B.x;
return A.y < B.y;
}
double cross_product(const Point& O, const Point& A, const Point& B) { //prdus vectorial
return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int h;
cin >> h;
vector<Point> points(h);
for (int i = 0; i < h; i++) {
cin >> points[i].x >> points[i].y;
}
sort(points.begin(), points.end(), comp);
vector<Point> st;
for (int i = 0; i < h; i++) { //parcurgem de la 0 la h - 1
while (st.size() >= 2 && cross_product(st[st.size()-2], st[st.size()-1], points[i]) <= precizie) //verificam sa fie destule puncte in stiva, calculam produsul vectorial si comparam cu precizia
st.pop_back();
st.push_back(points[i]);
}
long long st_size = st.size();
for (int i = h - 2; i >= 0; i--) { //parcurgem de la h - 2 la 0
while (st.size() > st_size && cross_product(st[st.size()-2], st[st.size()-1], points[i]) <= precizie) //verificam sa fie destule puncte in stiva, calculam produsul vectorial si comparam cu precizia
st.pop_back();
st.push_back(points[i]);
}
if (st.size() > 1 && fabs(st.front().x - st.back().x) < precizie && fabs(st.front().y - st.back().y) < precizie) st.pop_back(); //daca luam primul/ultimul punct de 2 ori
cout << st.size() << '\n';
cout << setprecision(6) << fixed;
for (long long i = 0; i < st.size(); i++) {
cout << st[i].x << ' ' << st[i].y << '\n';
}
return 0;
}