Cod sursa(job #3301116)

Utilizator AxkyroMiron Victor Eusebiu Axkyro Data 21 iunie 2025 19:44:09
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 2.31 kb
#include <stdio.h>
#include <stdlib.h>

#define MAXN 120000

typedef struct {
    double x, y;
} Punct;

Punct P[MAXN];
int st[MAXN];
int N, k = 0;

// calculeaza determinantul pentru 3 puncte
double det(Punct A, Punct B, Punct C) {
    return A.x * (B.y - C.y) + B.x * (C.y - A.y) + C.x * (A.y - B.y);
}

int cmp(const void *a, const void *b) {
    Punct *pa = (Punct *) a;
    Punct *pb = (Punct *) b;
    double d = det(P[0], *pa, *pb);
    if (d > 0) return -1;
    else if (d < 0) return 1;
    else {
        // coliniare comparam distante
        double dist_a = (pa->x - P[0].x) * (pa->x - P[0].x) + (pa->y - P[0].y) * (pa->y - P[0].y);
        double dist_b = (pb->x - P[0].x) * (pb->x - P[0].x) + (pb->y - P[0].y) * (pb->y - P[0].y);
        if (dist_a < dist_b) return -1;
        else if (dist_a > dist_b) return 1;
        else return 0;
    }
}

int main() {
    FILE *input = fopen("infasuratoare.in", "r");
    FILE *output = fopen("infasuratoare.out", "w");
    if (!input || !output) {
        fprintf(stderr, "eroare deschidere fisiere!\n");
        exit(-1);
    }

    // citim n
    if (fscanf(input, "%d", &N) != 1) {
        fprintf(stderr, "eroare citire N!\n");
        exit(-1);
    }

    // citim punctele
    for (int i = 0; i < N; i++) {
        if (fscanf(input, "%lf %lf", &P[i].x, &P[i].y) != 2) {
            fprintf(stderr, "eroare citire puncte!\n");
            exit(-1);
        }
    }

    // gasim punctul cel mai jos si la stanga
    int leftmost = 0;
    for (int i = 1; i < N; i++) {
        if (P[i].y < P[leftmost].y || (P[i].y == P[leftmost].y && P[i].x < P[leftmost].x)) {
            leftmost = i;
        }
    }

    // mutam punctul in pozitia 0
    Punct temp = P[0];
    P[0] = P[leftmost];
    P[leftmost] = temp;

    // sortam punctele dupa unghiul polar
    qsort(P + 1, N - 1, sizeof(Punct), cmp);

    // construim infasuratoarea
    st[k++] = 0;
    st[k++] = 1;
    for (int i = 2; i < N; i++) {
        while (k > 1 && det(P[st[k - 2]], P[st[k - 1]], P[i]) <= 0) {
            k--;
        }
        st[k++] = i;
    }

    fprintf(output, "%d\n", k);
    for (int i = 0; i < k; i++) {
        fprintf(output, "%.6f %.6f\n", P[st[i]].x, P[st[i]].y);
    }

    fclose(input);
    fclose(output);
    return 0;
}