Cod sursa(job #3358138)

Utilizator Marius08Marius Benea Marius08 Data 14 iunie 2026 21:23:36
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    double x, y;
} Punct;

int comp(const void *a, const void *b) {
    const Punct *p1 = a;
    const Punct *p2 = b;

    if (p1->x != p2->x)
        return (p1->x > p2->x) ? 1 : -1;
    if (p1->y != p2->y)
        return (p1->y > p2->y) ? 1 : -1;
    return 0;
}

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

int main() {
    FILE *fin = NULL;
    fin = fopen("infasuratoare.in", "r");
    if(fin == NULL)
        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), comp);

    Punct *st = malloc(2 * N * sizeof(Punct));
    int k = 0;
    for(int i = 0;i < N; i ++) {
        while(k > 1 && cross(st[k-2], st[k-1], puncte[i]) <= 0)
            k--;
        st[k] = puncte[i];
        k ++;
    }

    int li = k+1;
    for(int i = N-2; i >= 0; i--) {
        while(k >= li && cross(st[k-2], st[k-1], puncte[i]) <= 0)
            k --;
        st[k] = puncte[i];
        k ++;
    }
    k --;

    FILE *fout = NULL;
    fout = fopen("infasuratoare.out", "w");
    if(fout == NULL) {
        free(puncte);
        free(st);
        return -1;
    }
    fprintf(fout, "%d\n", k);
    for(int i = 0; i < k; i ++)
        fprintf(fout, "%lf %lf\n", st[i].x, st[i].y);

    free(puncte);
    free(st);
    fclose(fin);
    return 0;
}