Cod sursa(job #3358742)

Utilizator Cosma_Laura_IoanaCosma Laura-Ioana Cosma_Laura_Ioana Data 19 iunie 2026 19:05:11
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.73 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define EPS 1e-9 // marja de eroare (numar foarte mic)

// punct 2D
typedef struct {
    double x, y;
} Punct;

double produs_vectorial(Punct O, Punct A, Punct B)
{
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

int comparare_puncte(const void *a, const void *b) // pentru qsort
{
    Punct *p1 = (Punct *)a;
    Punct *p2 = (Punct *)b;

    if (fabs(p1->x - p2->x) > EPS) // sortez dupa coordonatele x
    {
        if (p1->x < p2->x) return -1;
        else return 1;
    }
    if (fabs(p1->y - p2->y) > EPS) // daca coordonatele x sunt = sortez dupa y
    {
        if (p1->y < p2->y) return -1;
        else return 1;
    }
    return 0;
}

int main()
{
    FILE *fin = fopen("infasuratoare.in", "r");
    FILE *fout = fopen("infasuratoare.out", "w");
    int n;
    if (fscanf(fin, "%d", &n) != 1) return 1;

    Punct *P = (Punct *)malloc(n * sizeof(Punct));
    for (int i = 0; i < n; i++)
    {
        fscanf(fin, "%lf %lf", &P[i].x, &P[i].y);
    }

    qsort(P, n, sizeof(Punct), comparare_puncte);

    Punct *H = (Punct *)malloc(2 * n * sizeof(Punct));
    int k = 0;

    for (int i = 0; i < n; ++i)
    {
        while (k >= 2 && produs_vectorial(H[k - 2], H[k - 1], P[i]) <= EPS)
        {
            k--;
        }
        H[k++] = P[i];
    }

    int limita = k +1;
    for (int i = n - 2; i >= 0; i--)
    {
        while (k>=limita && produs_vectorial(H[k-2], H[k-1], P[i]) <= EPS)
        {
            k--;
        }
        H[k++] = P[i];
    }
    k--;

    fprintf(fout, "%d\n", k);
    for (int i = 0; i < k; i++)
    {
        fprintf(fout, "%.6lf %.6lf\n", H[i].x, H[i].y);
    }

    free(P);
    free(H);
    fclose(fin);
    fclose(fout);
    return 0;
}