Cod sursa(job #3232956)

Utilizator VladimirGVladimir Ghimpau VladimirG Data 2 iunie 2024 08:35:19
Problema Infasuratoare convexa Scor 0
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.86 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define in "infasuratoare.in"
#define out "infasuratoare.out"

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

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

double distanta(Punct A, Punct B)
{
    return sqrt((B.x - A.x) * (B.x - A.x) + (B.y - A.y) * (B.y - A.y));
}

int compara(const void *a, const void *b)
{
    Punct A = *((Punct *)a);
    Punct B = *((Punct *)b);
    double unghiA = atan2(A.y, A.x);
    double unghiB = atan2(B.y, B.x);
    if (unghiA < unghiB)
        return -1;
    if (unghiA > unghiB)
        return 1;
    return 0;
}

void acoperireConvexa(Punct P[], int n, FILE *fout)
{
    if (n < 3)
        return;

    int minIdx = 0;
    for (int i = 1; i < n; i++)
    {
        if (P[i].y < P[minIdx].y || (P[i].y == P[minIdx].y && P[i].x < P[minIdx].x))
        {
            minIdx = i;
        }
    }

    Punct temp = P[0];
    P[0] = P[minIdx];
    P[minIdx] = temp;

    qsort(&P[1], n - 1, sizeof(Punct), compara);

    Punct *stiva = (Punct *)malloc(n * sizeof(Punct));
    int top = 2;
    stiva[0] = P[0];
    stiva[1] = P[1];
    stiva[2] = P[2];

    for (int i = 3; i < n; i++)
    {
        while (produsVectorial(stiva[top - 1], stiva[top], P[i]) <= 0)
        {
            top--;
        }
        top++;
        stiva[top] = P[i];
    }

    fprintf(fout, "%d\n", top + 1);

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

    free(stiva);
}

int main()
{
    FILE *fin, *fout;
    fin = fopen(in, "r");
    fout = fopen(out, "w");
    int N, i;
    fscanf(fin, "%d", &N);
    Punct P[N];
    for (i = 0; i < N; i++)
    {
        fscanf(fin, "%lf %lf", &P[i].x, &P[i].y);
    }
    acoperireConvexa(P, N, fout);
    fclose(fin);
    fclose(fout);
    return 0;
}