Cod sursa(job #3358681)

Utilizator Ilie_Andra_MariaIlie Andra Maria Ilie_Andra_Maria Data 19 iunie 2026 14:38:29
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.84 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct
{
    double x;
    double y;
} punct;

punct puncte[120005];
punct infasuratoare[240005];

double determinant(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(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 main()
{
    FILE *fin = fopen("infasuratoare.in", "r");
    FILE *fout = fopen("infasuratoare.out", "w");

    int n;
    fscanf(fin, "%d", &n);

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

    qsort(puncte, n, sizeof(punct), compara);

    int nr_puncte = 0;

    for (int i = 0; i < n; i++)
    {
        while (nr_puncte >= 2 &&
               determinant(infasuratoare[nr_puncte - 2], infasuratoare[nr_puncte - 1], puncte[i]) <= 0)
        {
            nr_puncte--;
        }

        infasuratoare[nr_puncte++] = puncte[i];
    }

    int inceput_parte_superioara = nr_puncte + 1;

    for (int i = n - 2; i >= 0; i--)
    {
        while (nr_puncte >= inceput_parte_superioara && determinant(infasuratoare[nr_puncte - 2], infasuratoare[nr_puncte - 1], puncte[i]) <= 0)
        {
            nr_puncte--;
        }

        infasuratoare[nr_puncte++] = puncte[i];
    }

    nr_puncte--;

    fprintf(fout, "%d\n", nr_puncte);

    for (int i = 0; i < nr_puncte; i++)
    {
        fprintf(fout, "%.6f %.6f\n", infasuratoare[i].x, infasuratoare[i].y);
    }

    fclose(fin);
    fclose(fout);

    return 0;
}