Pagini recente » elfus/editorial-runda-9 | Cod sursa (job #2084020) | Cod sursa (job #1345048) | Cod sursa (job #1216237) | Cod sursa (job #1647629)
#include <cstdio>
#include <algorithm>
using namespace std;
#define NMAX 120005
#define eps 1e-12
struct point {
double x;
double y;
};
struct line {
double a;
double b;
double c;
};
point p[NMAX];
point hull[NMAX];
point st[NMAX];
int n, k;
bool point_sort(point a, point b) {
return a.y < b.y;
}
inline int cmp(double a, double b) {
double c = a - b;
if(c < -eps) return -1;
if(c > eps) return 1;
return 0;
}
inline line get_line(point p1, point p2) {
line l;
l.a = p1.y - p2.y;
l.b = p2.x - p1.x;
l.c = p1.x * p2.y - p2.x * p1.y;
return l;
}
int side(line l, point p) {
return cmp(l.a * p.x + l.b * p.y, -l.c);
}
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int i, j;
scanf("%d", &n);
for(i = 1; i <= n; i++) {
scanf("%lf %lf", &p[i].x, &p[i].y);
}
sort(p+1, p+n+1, point_sort);
st[1] = p[1];
st[2] = p[2];
k = 2;
for(i = 3; i <= n; i++) {
while(k >= 2 && side(get_line(st[k - 1], st[k]), p[i]) <= 0) {
k--;
}
st[++k] = p[i];
}
j = 0;
for(i = 1; i < k; i++) {
hull[++j] = st[i];
}
st[1] = p[n];
st[2] = p[n - 1];
k = 2;
for(i = n - 2; i > 0; i--) {
while(k >= 2 && side(get_line(st[k - 1], st[k]), p[i]) <= 0) {
k--;
}
st[++k] = p[i];
}
for(i = 1; i < k; i++) {
hull[++j] = st[i];
}
printf("%d\n", j);
for(i = 1; i <= j; i++) {
printf("%f %f\n", hull[i].x, hull[i].y);
}
return 0;
}