Pagini recente » Cod sursa (job #679756) | Cod sursa (job #1149030) | Cod sursa (job #1315696) | Cod sursa (job #3358261) | Cod sursa (job #3309271)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int NMAX = 120005;
const long double EPS = 1e-12;
struct Point {
long double x, y;
};
long double cp(Point A, Point B, Point C) {
return (B.y - A.y) * (C.x - A.x) - (C.y - A.y) * (B.x - A.x);
}
bool cmp(Point &A, Point &B) {
return A.x < B.x || (A.x == B.x && A.y < B.y);
}
int N;
Point v[NMAX];
int main() {
fin >> N;
for (int i = 0; i < N; i++) {
fin >> v[i].x >> v[i].y;
}
sort(v, v + N, cmp);
vector<Point> upper_hull;
upper_hull.push_back(v[0]);
upper_hull.push_back(v[1]);
for (int i = 2; i < N; i++) {
while (upper_hull.size() >= 2 && cp(upper_hull[upper_hull.size() - 2], upper_hull[upper_hull.size() - 1], v[i]) < EPS) {
upper_hull.pop_back();
}
upper_hull.push_back(v[i]);
}
vector<Point> lower_hull;
lower_hull.push_back(v[N - 1]);
lower_hull.push_back(v[N - 2]);
for (int i = N - 3; i >= 0; i--) {
while (lower_hull.size() >= 2 && cp(lower_hull[lower_hull.size() - 2], lower_hull[lower_hull.size() - 1], v[i]) < EPS) {
lower_hull.pop_back();
}
lower_hull.push_back(v[i]);
}
reverse(lower_hull.begin(), lower_hull.end());
reverse(upper_hull.begin(), upper_hull.end());
lower_hull.pop_back();
upper_hull.pop_back();
vector<Point> hull = lower_hull;
hull.insert(hull.end(), upper_hull.begin(), upper_hull.end());
fout << hull.size() << '\n';
fout << fixed;
for (int i = 0; i < hull.size(); i++) {
fout << setprecision(12) << hull[i].x << ' ' << hull[i].y << '\n';
}
return 0;
}