Cod sursa(job #3358999)

Utilizator Chesa.DavidChesa David Chesa.David Data 22 iunie 2026 20:07:35
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <stdio.h>
#include <stdlib.h>
#define MAXN 120001
typedef long double ld;

typedef struct {
    ld x, y;
    int idx; 
} Point;

int cmp(const void *a, const void *b) {
    Point *p = (Point*)a, *q = (Point*)b;
    if (p->x != q->x) return (p->x > q->x) - (p->x < q->x);
    return (p->y > q->y) - (p->y < q->y);
}
ld cross(Point O, Point A, Point B) {
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}


Point pts[MAXN], hull[2 * MAXN];
int n, h;

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

    fscanf(fin, "%d", &n);
    for (int i = 0; i < n; i++) {
        fscanf(fin, "%Lf %Lf", &pts[i].x, &pts[i].y);
        pts[i].idx = i;
    }
    qsort(pts, n, sizeof(Point), cmp);
    h = 0;
    for (int i = 0; i < n; i++) {
        while (h >= 2 && cross(hull[h-2], hull[h-1], pts[i]) <= 0)
            h--;
        hull[h++] = pts[i];
    }
    int lower_size = h;
    for (int i = n-2; i >= 0; i--) {
        while (h > lower_size && cross(hull[h-2], hull[h-1], pts[i]) <= 0)
            h--;
        hull[h++] = pts[i];
    }
    h--;

    fprintf(fout, "%d\n", h);
    for (int i = 0; i < h; i++)
        fprintf(fout, "%Lf %Lf\n", hull[i].x, hull[i].y);

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