Pagini recente » Cod sursa (job #1592742) | Cod sursa (job #2773623) | Cod sursa (job #2763611) | Cod sursa (job #741136) | Cod sursa (job #3359350)
#include <stdio.h>
#include <stdlib.h>
typedef struct {
double x, y;
} Punct;
int sorteaza(const void* a, const void* b) {
Punct* p1 = (Punct*)a;
Punct* p2 = (Punct*)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 orientare(Punct a, Punct b, Punct c) {
return (b.x - a.x) * (c.y - a.y)
- (b.y - a.y) * (c.x - a.x);
}
void adauga_in_stiva(Punct* stiva, int* top, Punct p) {
while (*top >= 2 && orientare(stiva[*top - 2], stiva[*top - 1], p) <= 0)
(*top)--;
stiva[(*top)++] = p;
}
int main() {
FILE* fin = fopen("infasuratoare.in", "r");
FILE* fout = fopen("infasuratoare.out", "w");
int n;
fscanf(fin, "%d", &n);
Punct* pts = (Punct*)malloc(n * sizeof(Punct));
for (int i = 0; i < n; i++)
fscanf(fin, "%lf %lf", &pts[i].x, &pts[i].y);
qsort(pts, n, sizeof(Punct), sorteaza);
Punct* hull = (Punct*)malloc(2 * n * sizeof(Punct));
int inf = 0, sup = 0;
/* Lower hull: stanga -> dreapta (sens orar, partea de jos) */
for (int i = 0; i < n; i++)
adauga_in_stiva(hull, &inf, pts[i]);
/* Upper hull: dreapta -> stanga (sens orar, partea de sus) */
for (int i = n - 2; i >= 0; i--)
adauga_in_stiva(hull + inf, &sup, pts[i]);
int hull_size = inf + sup;
fprintf(fout, "%d\n", hull_size);
/* Afisam in ordine inversa = sens trigonometric (anti-orar) */
for (int i = hull_size - 1; i >= 0; i--)
fprintf(fout, "%.6f %.6f\n", hull[i].x, hull[i].y);
free(pts);
free(hull);
fclose(fin);
fclose(fout);
return 0;
}