Cod sursa(job #3359394)

Utilizator poenar_rares_emanuelPoenar Rares Emanuel poenar_rares_emanuel Data 27 iunie 2026 18:03:05
Problema Infasuratoare convexa Scor 0
Compilator c-64 Status done
Runda Arhiva educationala Marime 2 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

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

Punct punct_referinta;

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

double distanta_patrat(Punct A,Punct B) {
    double dx=A.x-B.x;
    double dy=A.y-B.y;
    return dx*dx+dy*dy;
}

int compara_unghi(const void *a, const void *b) {
    Punct *pa=(Punct *)a;
    Punct *pb=(Punct *)b;

    double produs=produs_vectorial(punct_referinta,*pa,*pb);

    if (produs>0){
      return -1;  
    }
    if (produs<0){
      return  1;  
    }

    double dist_a=distanta_patrat(punct_referinta,*pa);
    double dist_b=distanta_patrat(punct_referinta,*pb);

    if (dist_a<dist_b){
      return -1;  
    }
    if (dist_a>dist_b){
        return  1;        
    }
    return 0;
}

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

    int n;
    fscanf(fin,"%d",&n);

    Punct *puncte=(Punct *)malloc(n*sizeof(Punct));
    for (int i=0;i<n;i++) {
        fscanf(fin,"%lf %lf",&puncte[i].x,&puncte[i].y);
    }
    int idx_start=0;
    for (int i=1;i<n;i++) {
        if (puncte[i].y<puncte[idx_start].y|| (puncte[i].y==puncte[idx_start].y&&puncte[i].x<puncte[idx_start].x)) {
            idx_start=i;
        }
    }
    Punct temp=puncte[0];
    puncte[0]=puncte[idx_start];
    puncte[idx_start]=temp;

    punct_referinta=puncte[0];

    qsort(puncte + 1, n - 1, sizeof(Punct), compara_unghi);

    Punct *stiva = (Punct *)malloc(n * sizeof(Punct));
    int top = 0; 
    stiva[top++] = puncte[0];
    stiva[top++] = puncte[1];
    for (int i = 2; i < n; i++) {
        while (top >= 2 && produs_vectorial(stiva[top - 2], stiva[top - 1], puncte[i]) <= 0) {
            top--;
        }
        stiva[top++] = puncte[i];
    }

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

    free(puncte);
    free(stiva);
    fclose(fin);
    fclose(fout);

    return 0;
}