Cod sursa(job #3301092)

Utilizator Tuduce_RobertTuduce Robert Florin Tuduce_Robert Data 21 iunie 2025 16:26:19
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    double x, y;
} Point;

int cmp(const void *a, const void *b) {
    Point *p1 = (Point *)a;
    Point *p2 = (Point *)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(Point O, Point A, Point B) {
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

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

    int N, i, k = 0;
    fscanf(fin, "%d", &N);

    Point *P = (Point *)malloc(N * sizeof(Point));
    Point *H = (Point *)malloc(2 * N * sizeof(Point));

    for (i = 0; i < N; i++) {
        fscanf(fin, "%lf %lf", &P[i].x, &P[i].y);
    }

    qsort(P, N, sizeof(Point), cmp);

    for (i = 0; i < N; i++) {
        while (k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
        H[k++] = P[i];
    }

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

    k--;

    fprintf(fout, "%d\n", k);
    for (i = 0; i < k; i++) {
        fprintf(fout, "%.10lf %.10lf\n", H[i].x, H[i].y);
    }

    free(P);
    free(H);
    fclose(fin);
    fclose(fout);

    return 0;
}