Cod sursa(job #3301078)

Utilizator abel3324Ursu Abel-Patrick abel3324 Data 21 iunie 2025 14:44:39
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 2.12 kb
#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;
}