Cod sursa(job #3359350)

Utilizator NeamtuFelixNeamtu Felix NeamtuFelix Data 27 iunie 2026 12:18:15
Problema Infasuratoare convexa Scor 0
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.71 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    double x, y;
} Punct;

int sorteaza(const void* a, const void* b) {
    Punct* p1 = (Punct*)a;
    Punct* p2 = (Punct*)b;
    if (p1->x < p2->x) return -1;
    if (p1->x > p2->x) return  1;
    if (p1->y < p2->y) return -1;
    if (p1->y > p2->y) return  1;
    return 0;
}

double orientare(Punct a, Punct b, Punct c) {
    return (b.x - a.x) * (c.y - a.y)
         - (b.y - a.y) * (c.x - a.x);
}

void adauga_in_stiva(Punct* stiva, int* top, Punct p) {
    while (*top >= 2 && orientare(stiva[*top - 2], stiva[*top - 1], p) <= 0)
        (*top)--;
    stiva[(*top)++] = p;
}

int main() {
    FILE* fin  = fopen("infasuratoare.in",  "r");
    FILE* fout = fopen("infasuratoare.out", "w");

    int n;
    fscanf(fin, "%d", &n);

    Punct* pts = (Punct*)malloc(n * sizeof(Punct));
    for (int i = 0; i < n; i++)
        fscanf(fin, "%lf %lf", &pts[i].x, &pts[i].y);

    qsort(pts, n, sizeof(Punct), sorteaza);

    Punct* hull = (Punct*)malloc(2 * n * sizeof(Punct));
    int inf = 0, sup = 0;

    /* Lower hull: stanga -> dreapta (sens orar, partea de jos) */
    for (int i = 0; i < n; i++)
        adauga_in_stiva(hull, &inf, pts[i]);

    /* Upper hull: dreapta -> stanga (sens orar, partea de sus) */
    for (int i = n - 2; i >= 0; i--)
        adauga_in_stiva(hull + inf, &sup, pts[i]);

    int hull_size = inf + sup;

    fprintf(fout, "%d\n", hull_size);

    /* Afisam in ordine inversa = sens trigonometric (anti-orar) */
    for (int i = hull_size - 1; i >= 0; i--)
        fprintf(fout, "%.6f %.6f\n", hull[i].x, hull[i].y);

    free(pts);
    free(hull);
    fclose(fin);
    fclose(fout);
    return 0;
}