Pagini recente » Cod sursa (job #2281345) | Cod sursa (job #1149692) | Cod sursa (job #1768384) | Cod sursa (job #2130979) | Cod sursa (job #3359277)
#include <stdio.h>
#include <stdlib.h>
#define MAXN 120005
typedef struct {
double x, y;
} Point;
Point p[MAXN];
Point hull[2 * MAXN];
int cmp(const void *a, const void *b) {
Point *A = (Point *)a;
Point *B = (Point *)b;
if (A->x < B->x)
return -1;
if (A->x > B->x)
return 1;
if (A->y < B->y)
return -1;
if (A->y > B->y)
return 1;
return 0;
}
double cross(Point a, Point b, Point c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%lf %lf", &p[i].x, &p[i].y);
}
qsort(p, n, sizeof(Point), cmp);
int m = 0;
for (int i = 0; i < n; i++) {
while (m >= 2 && cross(hull[m - 2], hull[m - 1], p[i]) <= 0)
m--;
hull[m++] = p[i];
}
int t = m + 1;
for (int i = n - 2; i >= 0; i--) {
while (m >= t && cross(hull[m - 2], hull[m - 1], p[i]) <= 0)
m--;
hull[m++] = p[i];
}
m--;
printf("%d\n", m);
for (int i = 0; i < m; i++) {
printf("%.6lf %.6lf\n", hull[i].x, hull[i].y);
}
return 0;
}