Pagini recente » Cod sursa (job #1662069) | Cod sursa (job #564282) | Cod sursa (job #564286) | Cod sursa (job #2133255) | Cod sursa (job #3301078)
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>
#define MAXN 1000007
typedef struct {
double x, y;
} point;
point puncte[MAXN];
point infasuratoare[2 * MAXN];
int cmp(const void* a, const void* b) {
point* p1 = (point*)a;
point* p2 = (point*)b;
if (p1->x != p2->x)
return (p1->x < p2->x) ? -1 : 1;
else
return (p1->y < p2->y) ? -1 : 1;
}
double prod_vect(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(void) {
FILE* fin = fopen("infasuratoare.in", "r");
FILE* fout = fopen("infasuratoare.out", "w");
if (fin == NULL || fout == NULL)
{
fprintf(stderr, "Eroare la deschiderea fisierelor\n");
return 1;
}
int N;
if (fscanf(fin, "%d", &N) != 1)
{
fprintf(stderr, "Eroare la citirea numarului de puncte\n");
return 1;
}
for (int i = 0; i < N; i++)
{
if (fscanf(fin, "%lf %lf", &puncte[i].x, &puncte[i].y) != 2) {
fprintf(stderr, "Eroare la citirea punctului %d\n", i);
return 1;
}
}
if (N == 1)
{
fprintf(fout, "1\n%.6lf %.6lf\n", puncte[0].x, puncte[0].y);
fclose(fin);
fclose(fout);
return 0;
}
qsort(puncte, N, sizeof(point), cmp);
int k = 0;
for (int i = 0; i < N; i++)
{
while (k >= 2 && prod_vect(infasuratoare[k - 2], infasuratoare[k - 1], puncte[i]) <= 0)
k--;
infasuratoare[k++] = puncte[i];
}
int t = k + 1;
for (int i = N - 2; i >= 0; i--)
{
while (k >= t && prod_vect(infasuratoare[k - 2], infasuratoare[k - 1], puncte[i]) <= 0)
k--;
infasuratoare[k++] = puncte[i];
}
k--;
fprintf(fout, "%d\n", k);
for (int i = 0; i < k; i++)
{
fprintf(fout, "%.6lf %.6lf\n", infasuratoare[i].x, infasuratoare[i].y);
}
if(fclose(fin))
{
fprintf(stderr,"eroare la inchidere");
exit(EXIT_FAILURE);
}
if(fclose(fout))
{
fprintf(stderr,"eroare la inchidere");
exit(EXIT_FAILURE);
}
return 0;
}