Pagini recente » Cod sursa (job #31651) | Cod sursa (job #2294688) | Cod sursa (job #2006511) | Cod sursa (job #2048118) | Cod sursa (job #1511985)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#define x first
#define y second
using namespace std;
typedef pair<double, double> point;
const int MAXN = 120001;
point pts[MAXN];
int n, hull[MAXN];
double cross_product(const point &O, const point &A, const point &B) {
double result = (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
return result;
}
int main()
{
#ifdef LOCAL
freopen("input", "r", stdin);
#else
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
#endif // LOCAL
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> pts[i].x >> pts[i].y;
}
sort(pts + 1, pts + n, [&O = pts[0]](const point &A, const point &B) {
return cross_product(O, A, B) < 0;
});
hull[0] = 0;
hull[1] = 1;
int k = 2;
for (int i = 2; i < n; ++i) {
while (k >= 2 && cross_product(pts[hull[k - 2]], pts[hull[k - 1]], pts[i]) > 0) {
--k;
}
hull[k] = i;
++k;
}
cout << k << '\n' << setprecision(6) << fixed;
for (int i = k - 1; i >= 0; --i) {
cout << pts[hull[i]].x << ' ' << pts[hull[i]].y << '\n';
}
return 0;
}