Pagini recente » Cod sursa (job #1251848) | Cod sursa (job #3358750) | Cod sursa (job #1251835) | Cod sursa (job #733457) | Cod sursa (job #3358597)
// Link Problema: https://infoarena.ro/problema/infasuratoare
// Link Solutie:
#include <stdio.h>
#include <stdlib.h>
#define MAXN 120005
#define EPS 1e-12
typedef struct {
double x, y;
} Punct;
Punct puncte[MAXN];
Punct infasuratoare[2 * MAXN];
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);
}
int compara_puncte(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;
}
int construieste_infasuratoare(int n) {
qsort(puncte, n, sizeof(Punct), compara_puncte);
int k = 0;
for (int i = 0; i < n; i++) {
while (k >= 2 && orientare(infasuratoare[k - 2], infasuratoare[k - 1], puncte[i]) <= EPS) {
k--;
}
infasuratoare[k++] = puncte[i];
}
int limita_inferioara = k + 1;
for (int i = n - 2; i >= 0; i--) {
while (k >= limita_inferioara && orientare(infasuratoare[k - 2], infasuratoare[k - 1], puncte[i]) <= EPS) {
k--;
}
infasuratoare[k++] = puncte[i];
}
k--;
return k;
}
int main() {
FILE *fin = fopen("infasuratoare.in", "r");
FILE *fout = fopen("infasuratoare.out", "w");
if (fin == NULL || fout == NULL) {
printf("Eroare la deschiderea fisierelor!\n");
if (fin) fclose(fin);
if (fout) fclose(fout);
return 1;
}
int n;
if (fscanf(fin, "%d", &n) != 1) {
printf("Eroare la citirea lui N!\n");
fclose(fin);
fclose(fout);
return 1;
}
for (int i = 0; i < n; i++) {
if (fscanf(fin, "%lf %lf", &puncte[i].x, &puncte[i].y) != 2) {
printf("Eroare la citirea coordonatelor punctelor!\n");
fclose(fin);
fclose(fout);
return 1;
}
}
int dimensiune_finala = construieste_infasuratoare(n);
fprintf(fout, "%d\n", dimensiune_finala);
for (int i = 0; i < dimensiune_finala; i++) {
fprintf(fout, "%.6f %.6f\n", infasuratoare[i].x, infasuratoare[i].y);
}
fclose(fin);
fclose(fout);
return 0;
}