Cod sursa(job #3357104)

Utilizator Sonia.06Braila Sonia Biliana Sonia.06 Data 6 iunie 2026 13:31:16
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct{
    double x,y;
}punct;

int compara(const void * a, const void * b)
{
    punct *p1=(punct*)a;
    punct *p2=(punct*)b;
    if(p1->x != p2->x)
    {
        return (p1->x > p2->x) - (p1->x < p2->x);
    }
    return (p1->y > p2->y)-(p1->y < p2->y);
}

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

int main()
{
    FILE *f,*g;
    if((f=fopen("infasuratoare.in", "r"))==NULL)
    {
        fprintf(stderr, "eroare deschidere fisier\n");
        exit(1);
    }
    if((g=fopen("infasuratoare.out", "w"))==NULL)
    {
        fprintf(stderr, "eroare deschidere fisier\n");
        exit(1);
    }

    int n;
    if(fscanf(f,"%d", &n)!=1)
        return 0;

    punct puncte[120001];
    for(int i=0; i<n; i++)
    {
        fscanf(f,"%lf %lf", &puncte[i].x, &puncte[i].y);
    }
    qsort(puncte, n, sizeof(punct), compara);

    int H=0;
    punct *hull=(punct*)malloc(2*n*sizeof(punct));

    for (int i=0; i<n; i++)  //partea de sus
    {
        while (H>=2 && produs(hull[H-2], hull[H-1], puncte[i]) <= 1e-12)
            H--;
        hull[H++]=puncte[i];
    }

    int jos=H;
    for (int i=n-2; i>=0; i--) // partea de jos
    {
        while (H>jos && produs(hull[H-2], hull[H-1], puncte[i]) <= 1e-12) {
            H--;
        }
        hull[H++]=puncte[i];
    }

    if (n>1)
        H--;
    fprintf(g,"%d\n", H);
    for(int i=0; i<H; i++)
    {
        fprintf(g, "%lf %lf\n", hull[i].x, hull[i].y);
    }
    free(hull);
    fclose(f);
    fclose(g);
    return 0;
}