Cod sursa(job #3359392)

Utilizator gratian-stefan.tothToth Gratian-Stefan gratian-stefan.toth Data 27 iunie 2026 17:49:37
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 2 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) {
        return (p1->x < p2->x) ? -1 : 1;
    }
    if (p1->y != p2->y) {
        return (p1->y < p2->y) ? -1 : 1;
    }
    return 0;
}

double crossProduct(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");

    if (!fin || !fout) return 0;

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

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

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

    Point* hull = (Point*)malloc(2 * n * sizeof(Point));
    int h_size = 0;

    for (int i = 0; i < n; ++i) {
        while (h_size >= 2 && crossProduct(hull[h_size - 2], hull[h_size - 1], points[i]) <= 1e-11) {
            h_size--;
        }
        hull[h_size++] = points[i];
    }

    int lower_size = h_size;
    for (int i = n - 2; i >= 0; --i) {
        while (h_size > lower_size && crossProduct(hull[h_size - 2], hull[h_size - 1], points[i]) <= 1e-11) {
            h_size--;
        }
        hull[h_size++] = points[i];
    }

    if (h_size > 1) {
        h_size--;
    }

    int start_idx = 0;
    for (int i = 1; i < h_size; ++i) {
        if (hull[i].y < hull[start_idx].y || (hull[i].y == hull[start_idx].y && hull[i].x < hull[start_idx].x)) {
            start_idx = i;
        }
    }

    fprintf(fout, "%d\n", h_size);
    for (int i = 0; i < h_size; ++i) {
        int idx = (start_idx + i) % h_size;
        fprintf(fout, "%.6f %.6f\n", hull[idx].x, hull[idx].y);
    }

    free(points);
    free(hull);
    fclose(fin);
    fclose(fout);

    return 0;
}