Cod sursa(job #3359414)

Utilizator VasiesAnaMariaVasies Ana-Maria VasiesAnaMaria Data 27 iunie 2026 20:37:09
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 2.04 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct{
    long double x,y;
}Punct;

int compara(const void *a,const void *b){
    Punct *p=(Punct*)a,*q=(Punct*)b;
    if(p->x<q->x) return -1;
    if(p->x>q->x) return 1;
    if(p->y<q->y) return -1;
    if(p->y>q->y) return 1;
    return 0;
}

long 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 *fin=fopen("infasuratoare.in","r");
    if(fin==NULL){
        printf("Eroare la deschiderea fisierului de intrare\n");
        exit(EXIT_FAILURE);
    }

    FILE *fout=fopen("infasuratoare.out","w");
    if(fout==NULL){
        printf("Eroare la deschiderea fisierului de iesire\n");
        fclose(fin);
        exit(EXIT_FAILURE);
    }

    int n;
    if(fscanf(fin,"%d",&n)!=1){
        printf("Citire gresita a numarului de puncte\n");
        fclose(fin);
        fclose(fout);
        exit(EXIT_FAILURE);
    }

    Punct *v=malloc(n*sizeof(Punct));
    Punct *sol=malloc((2*n+1)*sizeof(Punct));

    for(int i=0;i<n;i++)
        if(fscanf(fin,"%Lf%Lf",&v[i].x,&v[i].y)!=2){
            printf("Citire gresita a coordonatelor\n");
            free(v);
            free(sol);
            fclose(fin);
            fclose(fout);
            exit(EXIT_FAILURE);
        }

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

    int k=0;
    for(int i=0;i<n;i++){
        while(k>=2&&produs(sol[k-2],sol[k-1],v[i])<=0) k--;
        sol[k++]=v[i];
    }

    int jos=k;
    for(int i=n-2;i>=0;i--){
        while(k>jos&&produs(sol[k-2],sol[k-1],v[i])<=0) k--;
        sol[k++]=v[i];
    }

    k--;

    fprintf(fout,"%d\n",k);
    for(int i=0;i<k;i++)
        fprintf(fout,"%.12Lf %.12Lf\n",sol[i].x,sol[i].y);

    free(v);
    free(sol);
    if(fclose(fin)!=0){
        printf("Eroare la inchiderea fisierului de intrare\n");
        exit(EXIT_FAILURE);
    }
    if(fclose(fout)!=0){
        printf("Eroare la inchiderea fisierului de iesire\n");
        exit(EXIT_FAILURE);
    }
    return 0;
}