Cod sursa(job #3358597)

Utilizator bree.vtxKohl Briana bree.vtx Data 18 iunie 2026 11:58:34
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 2.31 kb
// 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;
}