Pagini recente » Cod sursa (job #1280281) | Cod sursa (job #1833150) | Cod sursa (job #2099402) | Cod sursa (job #488411) | Cod sursa (job #3349260)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
using T = double;
const T EPS = 1e-15;
int sgn(T x) {
return (x >= -EPS) - (x <= EPS);
}
struct Point {
T x, y;
bool operator<(const Point& rhs) const {
if (abs(x - rhs.x) < EPS) {
return y < rhs.y;
} else {
return x < rhs.x;
}
}
};
T area(Point a, Point b, Point c) {
return a.x * b.y - a.x * c.y + b.x * c.y - b.x * a.y + c.x * a.y - c.x * b.y;
}
vector<Point> half_envelope(vector<Point>& points, int which_half) {
vector<Point> env;
for (auto& p : points) {
while (env.size() >= 2
&& sgn(area(env[env.size() - 2], env[env.size() - 1], p)) == which_half) {
env.pop_back();
}
env.push_back(p);
}
return env;
}
int main() {
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int n; cin >> n;
vector<Point> v(n);
for (int i = 0; i < n; i++) {
cin >> v[i].x >> v[i].y;
}
sort(v.begin(), v.end());
vector<Point> upper = half_envelope(v, -1);
vector<Point> lower = half_envelope(v, 1);
lower.pop_back();
reverse(lower.begin(), lower.end());
lower.pop_back();
upper.insert(upper.end(), lower.begin(), lower.end());
cout << upper.size() << "\n";
cout << fixed << setprecision(14);
for (auto& p : upper) {
cout << p.x << " " << p.y << "\n";
}
return 0;
}