Pagini recente » Cod sursa (job #2345066) | Cod sursa (job #1222492) | Cod sursa (job #1605558) | Cod sursa (job #91248) | Cod sursa (job #800879)
Cod sursa(job #800879)
#include <cstdio>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<double, double> Point;
const int N = 120005;
int n, nr;
Point v[N], stack[N];
void read() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%lf%lf", &v[i].x, &v[i].y);
}
inline double cross_product(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);
}
inline bool cmp(const Point& p1, const Point& p2) {
return cross_product(v[1], p1, p2) < 0;
}
void set_points() {
int pos = 1;
for (int i = 2; i <= n; ++i)
if (v[i] < v[pos])
pos = i;
swap(v[1], v[pos]);
sort(v + 2, v + n + 1, cmp);
}
void convex_hull() {
set_points();
stack[1] = v[1];
stack[2] = v[2];
nr = 2;
for (int i = 3; i <= n; ++i) {
while (nr >= 2 && cross_product(stack[nr - 1], stack[nr], v[i]) > 0)
--nr;
stack[++nr] = v[i];
}
}
void write() {
printf("%d\n", nr);
for (int i = nr; i > 0; --i)
printf("%.6lf %.6lf\n", stack[i].x, stack[i].y);
}
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out" ,"w", stdout);
read();
convex_hull();
write();
return 0;
}