Cod sursa(job #3301129)

Utilizator oana_vlasaOana Vlasa oana_vlasa Data 21 iunie 2025 20:22:09
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <stdio.h>
#include <stdlib.h>
#define MAX 120005

typedef struct
{
    double x, y;
} Punct;
Punct p[MAX], ch[2 * MAX];
int n, h;
// compară două puncte pentru sortare lexicografică
int cmp(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;

}
// produsul încrucișat
double orient(Punct a, Punct b, Punct c)
{
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

void convex_hull()
{
    qsort(p, n, sizeof(Punct), cmp);
    int i, t = 0;
    // partea de jos
    for (i = 0; i < n; i++)
    {
        while (h >= 2 && orient(ch[h - 2], ch[h - 1], p[i]) <= 0)
            h--;
        ch[h++] = p[i];
    }
    // partea de sus
    t = h + 1;
    for (i = n - 2; i >= 0; i--)
    {
        while (h >= t && orient(ch[h - 2], ch[h - 1], p[i]) <= 0)
            h--;
        ch[h++] = p[i];
    }
    h--; // eliminăm ultimul punct (același cu primul)
}

int main() {
    FILE* fin = fopen("infasuratoare.in", "r");
    FILE* fout = fopen("infasuratoare.out", "w");
    if (fin == NULL)
    {
        perror("eroare la deschiderea fisierului");
        exit(-1);
    }
    if (fout == NULL)
    {
        perror("eroare la inchiderea fisierului");
        exit(-1);
    }
    fscanf(fin, "%d", &n);
    for (int i = 0; i < n; ++i)
        fscanf(fin, "%lf %lf", &p[i].x, &p[i].y);
    convex_hull();
    fprintf(fout, "%d\n", h);
    for (int i = 0; i < h; ++i)
        fprintf(fout, "%.6lf %.6lf\n", ch[i].x, ch[i].y);

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