Pagini recente » Cod sursa (job #1978915) | Cod sursa (job #3355140) | Cod sursa (job #2014938) | Cod sursa (job #2328534) | Cod sursa (job #3318090)
#include <bits/stdc++.h>
using namespace std;
struct Point {
double x, y;
bool operator<(const Point &other) const {
if (x == other.x) return y < other.y;
return x < other.x;
}
};
double cross(const Point &A, const Point &B, const Point &C) {
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
int main() {
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int N;
fin >> N;
vector<Point> pts(N);
for (int i = 0; i < N; i++) {
fin >> pts[i].x >> pts[i].y;
}
sort(pts.begin(), pts.end());
vector<Point> hull;
for (int i = 0; i < N; i++) {
while (hull.size() >= 2 && cross(hull[hull.size()-2], hull.back(), pts[i]) <= 0) {
hull.pop_back();
}
hull.push_back(pts[i]);
}
size_t lower_size = hull.size();
for (int i = N - 2; i >= 0; i--) {
while (hull.size() > lower_size && cross(hull[hull.size()-2], hull.back(), pts[i]) <= 0) {
hull.pop_back();
}
hull.push_back(pts[i]);
if (i == 0) break;
}
hull.pop_back();
fout << hull.size() << "\n";
fout << fixed << setprecision(6);
for (auto &p : hull) {
fout << p.x << " " << p.y << "\n";
}
return 0;
}