Cod sursa(job #3301041)

Utilizator maria_cimpocaMaria Cimpoca maria_cimpoca Data 21 iunie 2025 01:38:08
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 3.73 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h> 

#define MAX 120001

typedef struct
{
    double x, y;
}Coord;

unsigned long N, stanga = 0;
Coord puncte[MAX];

typedef Coord Element_t;

typedef struct
{
    Element_t st[MAX];
    size_t cap;
    int vf;  
}Stack_t;

Stack_t stack;

typedef enum ErrorCode
{
    PUSH_OK, STACK_EMPTY, STACK_FULL
}EC_t;

void interpretare_eroare(EC_t eroare)
{
    switch(eroare)
    {
        case 0:
        {
            printf("Elementul a ajuns in stiva cu succes!\n");
            break;
        }
        case 1:
        {
            printf("Stiva este goala!\n");
            break;
        }
        case 2:
        {
            printf("Stiva este plina!\n");
            break;
        }
        default:
            break;
    }
}

void push(Stack_t *stiva, Element_t nou)
{
    if(stiva->vf == (int)stiva->cap - 1)
    {
        EC_t eroare = STACK_FULL;
        interpretare_eroare(eroare);
        return;
    }
    else
    {
        (stiva->vf)++;
        stiva->st[stiva->vf] = nou;
    }
}

Element_t pop(Stack_t *stiva)
{
    Element_t data;

    if(stiva->vf == -1)
    {
        EC_t eroare = STACK_EMPTY;
        interpretare_eroare(eroare);
        return (Coord){0, 0};
    }
    else
    {
        data = stiva->st[stiva->vf];
        (stiva->vf)--;
        return data;
    }
}

double cross(Coord p1, Coord p2, Coord p3) 
{
    return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x);
}

int compare(const void* p1, const void* p2) 
{
    Coord punct1 = *(Coord*)p1, punct2 = *(Coord*)p2;
    double val = cross(puncte[0], punct1, punct2);
    
    if (val > 0)
        return -1;
        
    if (val < 0)
        return 1;
        
    double d1 = (punct1.x - puncte[0].x)*(punct1.x - puncte[0].x) + (punct1.y - puncte[0].y)*(punct1.y - puncte[0].y);
    double d2 = (punct2.x - puncte[0].x)*(punct2.x - puncte[0].x) + (punct2.y - puncte[0].y)*(punct2.y - puncte[0].y);
    
    if(d1 < d2)
        return -1;
    else
        return 1;
}

void citire(FILE *input)
{
    fscanf(input, "%lu", &N);
    
    if(N < 3)
    {
        printf("Prea putine puncte.");
        exit(-1);
    }
    
    for(int i = 0; i < N; i++)
    {
        fscanf(input, "%lf %lf", &puncte[i].x, &puncte[i].y);
        
        if(puncte[i].y < puncte[stanga].y || 
           (puncte[i].y == puncte[stanga].y && puncte[i].x < puncte[stanga].x))
            stanga = i;
    }
    
    Coord aux;
    aux = puncte[0];
    puncte[0] = puncte[stanga];
    puncte[stanga] = aux;
    
    qsort(puncte + 1, N - 1, sizeof(puncte[0]), compare);
}

void infasurare()
{
    push(&stack, puncte[0]);
    push(&stack, puncte[1]);
    
    for(int i = 2; i < N; i++)
    {
        while(stack.vf >= 1 && cross(stack.st[stack.vf - 1], stack.st[stack.vf], puncte[i]) <= 0)
            pop(&stack);
            
        push(&stack, puncte[i]);
    }
}

void afisare(FILE *output)
{
    fprintf(output, "%d\n", stack.vf + 1);

    for(int i = 0; i <= stack.vf; i++)
        fprintf(output, "%.12f %.12f\n", stack.st[i].x, stack.st[i].y);
}

int main()
{ 
    FILE *input, *output;
    
    if((input = fopen("infasuratoare.in", "r")) == NULL)
    {
        perror("Eroare la deschidere fisier intrare.");
        exit(-1);
    }
    
    citire(input);
    
    stack.cap = MAX;
    stack.vf = -1;
    
    infasurare();
    
    if((output = fopen("infasuratoare.out", "w")) == NULL)
    {
        perror("Eroare la deschidere fisier iesire.");
        exit(-1);
    } 
    
    afisare(output);    
        
    if(fclose(input) != 0)
    {
        perror("Eroare la inchidere fisier intrare.");
        exit(-1);
    }
    
    if(fclose(output) != 0)
    {
        perror("Eroare la inchidere fisier iesire.");
        exit(-1);
    }

    return 0;
}