Cod sursa(job #3359355)

Utilizator titus.ticusanTitusTicusan titus.ticusan Data 27 iunie 2026 13:05:34
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <stdio.h>
#include <stdlib.h>
// ALlgo lui Andrew?
#define eps 1e-9 // TOL pentru flt

typedef struct
{
    double x, y;
} Punct;

Punct puncte[120005];
Punct stiva[240005];

int compara(const void *a, const void *b)
{
    Punct *p1 = (Punct *)a;
    Punct *p2 = (Punct *)b;

    if (p1->x < p2->x - eps)
        return -1;
    if (p1->x > p2->x + eps)
        return 1;
    if (p1->y < p2->y - eps)
        return -1;
    if (p1->y > p2->y + eps)
        return 1;
    return 0;
}

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

int main()
{
    FILE *fin = fopen("infasuratoare.in", "r");
    FILE *fout = fopen("infasuratoare.out", "w");

    int n, i, k = 0, t;
    fscanf(fin, "%d", &n);

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

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

    for (i = 0; i < n; i++)
    {
        while (k >= 2 && produs(stiva[k - 2], stiva[k - 1], puncte[i]) <= eps)
        {
            k--;
        }
        stiva[k++] = puncte[i];
    }

    t = k + 1;
    for (i = n - 2; i >= 0; i--)
    {
        while (k >= t && produs(stiva[k - 2], stiva[k - 1], puncte[i]) <= eps)
        {
            k--;
        }
        stiva[k++] = puncte[i];
    }

    k--;

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

    fclose(fin);
    fclose(fout);
    return 0;
}