Pagini recente » Cod sursa (job #1047104) | Cod sursa (job #3358479) | Cod sursa (job #2222824) | Cod sursa (job #1107951) | Cod sursa (job #3359411)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX_N 120005
#define EPS 1e-12
typedef struct {
double x, y;
} Point;
Point P[MAX_N];
Point fig[2 * MAX_N];
int cmp(const void *a,const void *b) {
Point *p1 = (Point *)a;
Point *p2 = (Point *)b;
if (fabs(p1->x - p2->x) > EPS)
return (p1->x < p2->x) ? -1 : 1;
if (fabs(p1->y - p2->y) > EPS)
return (p1->y < p2->y) ? -1 : 1;
return 0;
}
double cross_product(Point O, Point A, Point B) {
return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.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 k = 0;
for (int i = 0; i < N; i++) {
while (k >= 2 && cross_product(fig[k - 2], fig[k - 1], P[i]) <= EPS) {
k--;
}
fig[k++] = P[i];
}
int t = k + 1;
for (int i = N - 2; i >= 0; i--) {
while (k >= t && cross_product(fig[k - 2], fig[k - 1], P[i]) <= EPS) {
k--;
}
fig[k++] = P[i];
}
k--;
int min_idx = 0;
for (int i = 1; i < k; i++) {
if (fig[i].y < fig[min_idx].y - EPS || (fabs(fig[i].y - fig[min_idx].y) <= EPS && fig[i].x < fig[min_idx].x - EPS)) {
min_idx = i;
}
}
printf("%d\n", k);
for (int i = 0; i < k; i++) {
int idx = (min_idx + i) % k;
printf("%.6lf %.6lf\n", fig[idx].x, fig[idx].y);
}
return 0;
}