Pagini recente » Cod sursa (job #1608529) | Cod sursa (job #383001) | Cod sursa (job #2062132) | Cod sursa (job #2064126) | Cod sursa (job #811392)
Cod sursa(job #811392)
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
inline int next_int() {
int d;
scanf("%d", &d);
return d;
}
inline double next_double() {
double f;
scanf("%lf", &f);
return f;
}
struct point {
double x, y;
point(double x = 0, double y = 0) :
x(x), y(y) {
}
bool operator<(const point & p) const {
return x != p.x ? x < p.x : y < p.y;
}
};
vector<point> poly;
vector<point> upper;
vector<point> lower;
vector<point> convx;
bool convex(const point & a, const point & b, const point & c) {
point p1(b.x - a.x, b.y - a.y);
point p2(c.x - a.x, c.y - a.y);
return (p1.x * p2.y - p1.y * p2.x) < 0;
}
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int n = next_int();
for (int i = 0; i < n; i++) {
double x = next_double();
double y = next_double();
poly.push_back(point(x, y));
}
sort(poly.begin(), poly.end());
for (int i = 0; i < n; i++) {
upper.push_back(poly[i]);
while (upper.size() > 2 && !convex(upper[upper.size() - 3], upper[upper.size() - 2], upper[upper.size() - 1])) {
upper.erase(upper.begin() + upper.size() - 2);
}
}
for (int i = n - 1; i >= 0; i--) {
lower.push_back(poly[i]);
while (lower.size() > 2 && !convex(lower[lower.size() - 3], lower[lower.size() - 2], lower[lower.size() - 1])) {
lower.erase(lower.begin() + lower.size() - 2);
}
}
for (int i = 0; i < int(upper.size()); i++) {
convx.push_back(upper[i]);
}
for (int i = 1; i < int(lower.size()) - 1; i++) {
convx.push_back(lower[i]);
}
reverse(convx.begin(), convx.end());
printf("%d\n", int(convx.size()));
for (size_t i = 0; i < convx.size(); i++) {
printf("%lf %lf\n", convx[i].x, convx[i].y);
}
return 0;
}