Cod sursa(job #3300904)

Utilizator david.ghesuDavid G david.ghesu Data 19 iunie 2025 21:08:22
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 {
    double x, y;
} punct;


int ordonare_puncte(const void *a, const void *b) 
{
    punct *p = (punct*) a;
    punct *q = (punct*) b;

    if(p->x < q->x) 
        return  -1;
    else if(p->x > q->x)
        return 1;
    else 
    {
        if(p->y < q->y) 
            return -1;
        else 
            return 1;
    }
    return 0;
}


double pvect(punct A, punct B, punct C) // produsul vectorial pt orientare
{
    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");
    FILE *fout = fopen("infasuratoare.out", "w");
    if(!fin || !fout) 
    {
        printf("nu s-a putut deschide un fisier!\n");
        return 1;
    }

    int N;
    fscanf(fin, "%d", &N);
    punct *puncte = malloc(N * sizeof(punct));
    for (int i = 0; i < N; i++)
        fscanf(fin, "%lf %lf", &puncte[i].x, &puncte[i].y);

    qsort(puncte, N, sizeof(punct), ordonare_puncte);

    
    punct *stiva = malloc(2 * N * sizeof(punct));
    int top = 0;

    // partea de jos
    for(int i = 0; i < N; i++) 
    {
        while(top >= 2) 
        {
            double orientare = pvect(stiva[top-2], stiva[top-1], puncte[i]);
            if(orientare <= 0)
                top--;
            else
                break;
        }
        stiva[top] = puncte[i];
        top++;
    }

    // partea de sus
    int limita = top;
    for(int i = N - 2; i >= 0; i--) 
    {
        while(top > limita) 
        {
            double orientare = pvect(stiva[top-2], stiva[top-1], puncte[i]);
            if(orientare <= 0)
                top--;
            else
                break;
        }
        stiva[top] = puncte[i];
        top++;
    }

    top--; 

    fprintf(fout, "%d\n", top);
    for(int i = 0; i < top; i++)
        fprintf(fout, "%.6lf %.6lf\n", stiva[i].x, stiva[i].y);
    
    free(puncte);
    free(stiva);
    fclose(fin);
    fclose(fout);
    return 0;
}