Pagini recente » Cod sursa (job #3359277) | Cod sursa (job #3357561) | Cod sursa (job #1100962) | Cod sursa (job #1148863) | Cod sursa (job #3359276)
#include <stdio.h>
#include <stdlib.h>
#define MAXN 120000
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 lower = m;
for (int i = n - 2; i >= 0; i--) {
while (m > lower && cross(hull[m - 2], hull[m - 1], p[i]) <= 0)
m--;
hull[m++] = p[i];
}
m--;
int start = 0;
for (int i = 1; i < m; i++) {
if (hull[i].y < hull[start].y ||
(hull[i].y == hull[start].y && hull[i].x < hull[start].x))
start = i;
}
printf("%d\n", m);
for (int k = 0; k < m; k++) {
int i = (start - k + m) % m;
printf("%.6f %.6f\n", hull[i].x, hull[i].y);
}
return 0;
}