Pagini recente » Cod sursa (job #3358135) | Cod sursa (job #3358157) | Cod sursa (job #3358144) | Cod sursa (job #3358140) | Cod sursa (job #3359419)
#include <stdio.h>
#include <stdlib.h>
typedef struct {
double x, y;
} Point;
Point H[240005];
Point P[120005];
int cmp(const void *a, const void *b) {
Point *p1 = (Point *)a;
Point *p2 = (Point *)b;
if (p1->x < p2->x) return -1;
if (p1->x > p2->x) return 1;
if (p1->y < p2->y) return -1;
if (p1->y > p2->y) return 1;
return 0;
}
double cross(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() {
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;
// Lower hull
for (int i = 0; i < N; i++) {
while (k >= 2 && cross(H[k - 2], H[k - 1], P[i]) <= 0)
k--;
H[k++] = P[i];
}
// Upper hull
int t = k + 1;
for (int i = N - 2; i >= 0; i--) {
while (k >= t && cross(H[k - 2], H[k - 1], P[i]) <= 0)
k--;
H[k++] = P[i];
}
k--; // ultimul punct este identic cu primul
printf("%d\n", k);
for (int i = 0; i < k; i++)
printf("%.6lf %.6lf\n", H[i].x, H[i].y);
return 0;
}