Cod sursa(job #3359398)

Utilizator Chesa.DavidChesa David Chesa.David Data 27 iunie 2026 18:48:39
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 4.03 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define PRAG_EPSILON 1e-12
#define LIMITA_MAXIMA 120005

long double vector_puncte[LIMITA_MAXIMA][2];
long double stiva_poligon[LIMITA_MAXIMA][2];

long double coord_baza_x, coord_baza_y;

long double produs_vectorial(long double x_a, long double y_a, long double x_b, long double y_b, long double x_c, long double y_c) 
{
    return (x_b - x_a) * (y_c - y_a) - (y_b - y_a) * (x_c - x_a);
}

long double calcul_distanta(long double orig_x, long double orig_y, long double dest_x, long double dest_y)
{
    return (orig_x - dest_x) * (orig_x - dest_x) + (orig_y - dest_y) * (orig_y - dest_y);
}

int comparator_unghiular(const void *element_a, const void *element_b) 
{
    long double *punct_1 = (long double*)element_a;
    long double *punct_2 = (long double*)element_b;

    long double rezultat_orientare = produs_vectorial(coord_baza_x, coord_baza_y, punct_1[0], punct_1[1], punct_2[0], punct_2[1]);

    if(rezultat_orientare < -PRAG_EPSILON)
        return -1;

    if(rezultat_orientare > PRAG_EPSILON)
        return 1;

    long double dist_1 = calcul_distanta(coord_baza_x, coord_baza_y, punct_1[0], punct_1[1]);
    long double dist_2 = calcul_distanta(coord_baza_x, coord_baza_y, punct_2[0], punct_2[1]);

    if(dist_1 < dist_2)
        return -1;

    if(dist_1 > dist_2)
        return 1;

    return 0;
}

int main() {
    FILE *fisier_intrare, *fisier_iesire;

    fisier_intrare = fopen("infasuratoare.in", "r");
    if(!fisier_intrare) 
    {
        fprintf(stderr, "Eroare la deschiderea fisierului de intrare");
        return -1;
    }

    fisier_iesire = fopen("infasuratoare.out", "w");
    if(!fisier_iesire) 
    {
        fprintf(stderr, "Eroare la deschiderea fisierului de iesire");
        fclose(fisier_intrare);
        return -1;
    }

    int numar_total_puncte;
    fscanf(fisier_intrare, "%d", &numar_total_puncte);

    int indice_minim = 1;

    for(int contor = 1; contor <= numar_total_puncte; contor++) 
    {
        fscanf(fisier_intrare, "%Lf %Lf", &vector_puncte[contor][0], &vector_puncte[contor][1]);

        if(vector_puncte[contor][0] < vector_puncte[indice_minim][0])
            indice_minim = contor;
        else if(vector_puncte[contor][0] == vector_puncte[indice_minim][0] && vector_puncte[contor][1] < vector_puncte[indice_minim][1])
            indice_minim = contor;
    }

    long double valoare_temporara;

    valoare_temporara = vector_puncte[1][0];
    vector_puncte[1][0] = vector_puncte[indice_minim][0];
    vector_puncte[indice_minim][0] = valoare_temporara;

    valoare_temporara = vector_puncte[1][1];
    vector_puncte[1][1] = vector_puncte[indice_minim][1];
    vector_puncte[indice_minim][1] = valoare_temporara;

    coord_baza_x = vector_puncte[1][0];
    coord_baza_y = vector_puncte[1][1];

    qsort(vector_puncte + 2, numar_total_puncte - 1, sizeof(vector_puncte[0]), comparator_unghiular);

    stiva_poligon[1][0] = vector_puncte[1][0];
    stiva_poligon[1][1] = vector_puncte[1][1];

    stiva_poligon[2][0] = vector_puncte[2][0];
    stiva_poligon[2][1] = vector_puncte[2][1];

    int dimensiune_stiva = 2;

    for(int contor = 3; contor <= numar_total_puncte; contor++) 
    {
        while(dimensiune_stiva >= 2 && produs_vectorial(stiva_poligon[dimensiune_stiva - 1][0], stiva_poligon[dimensiune_stiva - 1][1], stiva_poligon[dimensiune_stiva][0], stiva_poligon[dimensiune_stiva][1], vector_puncte[contor][0], vector_puncte[contor][1]) > PRAG_EPSILON)
            dimensiune_stiva--;

        dimensiune_stiva++;
        stiva_poligon[dimensiune_stiva][0] = vector_puncte[contor][0];
        stiva_poligon[dimensiune_stiva][1] = vector_puncte[contor][1];
    }

    fprintf(fisier_iesire, "%d\n", dimensiune_stiva);

    for(int contor = dimensiune_stiva; contor >= 1; contor--)
        fprintf(fisier_iesire, "%.9Lf %.9Lf\n", stiva_poligon[contor][0], stiva_poligon[contor][1]);

    fclose(fisier_intrare);
    fclose(fisier_iesire);

    return 0;
}