Cod sursa(job #3301117)

Utilizator oana_vlasaOana Vlasa oana_vlasa Data 21 iunie 2025 19:47:06
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.66 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;
}