Pagini recente » Monitorul de evaluare | Cod sursa (job #3359414) | Cod sursa (job #3359330) | Cod sursa (job #3359395)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct {
double x;
double y;
} Punct;
Punct punct_referinta;
double produs_vectorial(Punct O, Punct A, Punct B) {
return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
double distanta_patrat(Punct A, Punct B) {
double dx = A.x - B.x;
double dy = A.y - B.y;
return dx * dx + dy * dy;
}
int compara_unghi(const void *a, const void *b) {
Punct *pa = (Punct *)a;
Punct *pb = (Punct *)b;
double produs = produs_vectorial(punct_referinta, *pa, *pb);
if (produs > 0) return -1;
if (produs < 0) return 1;
double dist_a = distanta_patrat(punct_referinta, *pa);
double dist_b = distanta_patrat(punct_referinta, *pb);
if (dist_a < dist_b) return -1;
if (dist_a > dist_b) return 1;
return 0;
}
int main() {
FILE *fin = fopen("infasuratoare.in", "r");
FILE *fout = fopen("infasuratoare.out", "w");
int n;
fscanf(fin, "%d", &n);
Punct *puncte = (Punct *)malloc(n * sizeof(Punct));
for (int i = 0; i < n; i++) {
fscanf(fin, "%lf %lf", &puncte[i].x, &puncte[i].y);
}
int idx_start = 0;
for (int i = 1; i < n; i++) {
if (puncte[i].y < puncte[idx_start].y ||
(puncte[i].y == puncte[idx_start].y && puncte[i].x < puncte[idx_start].x)) {
idx_start = i;
}
}
Punct temp = puncte[0];
puncte[0] = puncte[idx_start];
puncte[idx_start] = temp;
punct_referinta = puncte[0];
qsort(puncte + 1, n - 1, sizeof(Punct), compara_unghi);
Punct *stiva = (Punct *)malloc(n * sizeof(Punct));
int top = 0;
stiva[top++] = puncte[0];
stiva[top++] = puncte[1];
for (int i = 2; i < n; i++) {
while (top >= 2 && produs_vectorial(stiva[top - 2], stiva[top - 1], puncte[i]) <= 0) {
top--;
}
stiva[top++] = puncte[i];
}
fprintf(fout, "%d\n", top);
for (int i = 0; i < top; i++) {
fprintf(fout, "%lf %lf\n", stiva[i].x, stiva[i].y);
}
free(puncte);
free(stiva);
fclose(fin);
fclose(fout);
return 0;
}