Cod sursa(job #3359395)

Utilizator poenar_rares_emanuelPoenar Rares Emanuel poenar_rares_emanuel Data 27 iunie 2026 18:05:20
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 2.07 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];
    }

    fprintf(fout, "%d\n", top);
    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;
}