Cod sursa(job #3300791)

Utilizator maria_cimpocaMaria Cimpoca maria_cimpoca Data 19 iunie 2025 02:17:04
Problema Infasuratoare convexa Scor 20
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h> 

#define MAX 120000

typedef struct
{
    float x, y;
}Coord;

float 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 main()
{ 
    int N, stanga = 0, index = 0;
    Coord puncte[MAX], infasuratoare[MAX];
    FILE *input, *output;
    
    if((input = fopen("infasuratoare.in", "r")) == NULL)
    {
        perror("Eroare la deschidere fisier intrare.");
        exit(-1);
    }
    
    fscanf(input, "%d", &N);

    for(int i = 0; i < N; i++)
    {
        fscanf(input, "%f %f", &puncte[i].x, &puncte[i].y);
        
        if(puncte[i].x < puncte[stanga].x)
            stanga = i;
        else if(puncte[i].x == puncte[stanga].x)
                if(puncte[i].y < puncte[stanga].y)
                    stanga = i;
    }
    
    int initial = stanga;
    
    do{
        infasuratoare[index++] = puncte[stanga];
        
        int q = (stanga + 1) % N;
        
        for(int i = 0; i < N; i++)
        {
            if(i == stanga)
                continue;

            if(cross(puncte[stanga], puncte[i], puncte[q]) > 0)
                q = i;
        }
        
        stanga = q;
    }while(stanga != initial);
    
    if((output = fopen("infasuratoare.out", "w")) == NULL)
    {
        perror("Eroare la deschidere fisier iesire.");
        exit(-1);
    }
    
    fprintf(output, "%d\n", index);
    
    for(int i = 0; i < index; i++)
        fprintf(output, "%f %f\n", infasuratoare[i].x, infasuratoare[i].y);
        
    if(fclose(input) == -1)
    {
        perror("Eroare la inchidere fisier intrare.");
        exit(-1);
    }
    
    if(fclose(output) == -1)
    {
        perror("Eroare la inchidere fisier iesire.");
        exit(-1);
    }

    return 0;
}