Cod sursa(job #3359280)

Utilizator Radulescu_BiancaRadulescu Bianca-Larisa Radulescu_Bianca Data 26 iunie 2026 14:56:40
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.96 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    double x, y;
} Point;

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

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

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

    int n;
    if (fscanf(fin, "%d", &n) != 1) {
        return 0;
    }

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

    qsort(pts, n, sizeof(Point), comparePoints);

    Point* lower = (Point*)malloc(n * sizeof(Point));
    int lower_size = 0;
    for (int i = 0; i < n; ++i) {
        while (lower_size >= 2 && cross_product(lower[lower_size - 2], lower[lower_size - 1], pts[i]) <= 1e-11) {
            lower_size--;
        }
        lower[lower_size++] = pts[i];
    }

    Point* upper = (Point*)malloc(n * sizeof(Point));
    int upper_size = 0;
    for (int i = n - 1; i >= 0; --i) {
        while (upper_size >= 2 && cross_product(upper[upper_size - 2], upper[upper_size - 1], pts[i]) <= 1e-11) {
            upper_size--;
        }
        upper[upper_size++] = pts[i];
    }

    lower_size--;
    upper_size--;

    int hull_size = lower_size + upper_size;
    fprintf(fout, "%d\n", hull_size);

    for (int i = 0; i < lower_size; ++i) {
        fprintf(fout, "%.6f %.6f\n", lower[i].x, lower[i].y);
    }
    for (int i = 0; i < upper_size; ++i) {
        fprintf(fout, "%.6f %.6f\n", upper[i].x, upper[i].y);
    }

    free(pts);
    free(lower);
    free(upper);

    fclose(fin);
    fclose(fout);
    return 0;
}