Pagini recente » Cod sursa (job #3301536) | Cod sursa (job #3312816) | Cod sursa (job #3312819) | Cod sursa (job #3312843) | Cod sursa (job #3359349)
#include <stdio.h>
#include <stdlib.h>
typedef struct {
double x, y;
} Punct;
/* Comparator pentru qsort: sortare dupa x, la egalitate dupa y */
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;
}
/* Semn: returneaza -1, 0 sau 1 dupa semnul produsului vectorial
ne spune daca c e la stanga, pe dreapta ab, sau coliniar */
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);
}
/* Adauga un punct in stiva, eliminand punctele care fac viraj la dreapta */
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;
if (fscanf(fin, "%d", &n) != 1) return 0;
Punct* pts = (Punct*)malloc(n * sizeof(Punct));
for (int i = 0; i < n; ++i)
fscanf(fin, "%lf %lf", &pts[i].x, &pts[i].y);
/* Sortam punctele dupa x, la egalitate dupa y */
qsort(pts, n, sizeof(Punct), sorteaza);
Punct* hull = (Punct*)malloc(2 * n * sizeof(Punct));
int inf = 0, sup = 0;
/* Lower hull: parcurgere stanga -> dreapta */
for (int i = 0; i < n; i++)
adauga_in_stiva(hull, &inf, pts[i]);
/* Upper hull: parcurgere dreapta -> stanga
scriem direct dupa lower hull in acelasi array */
for (int i = n - 2; i >= 0; i--)
adauga_in_stiva(hull + inf, &sup, pts[i]);
/* hull contine lower + upper, fara a repeta capetele */
int hull_size = inf + sup;
fprintf(fout, "%d\n", hull_size);
for (int i = 0; i < hull_size; i++)
fprintf(fout, "%.6f %.6f\n", hull[i].x, hull[i].y);
free(pts);
free(hull);
fclose(fin);
fclose(fout);
return 0;
}