Cod sursa(job #3359419)

Utilizator Lupu_Mirabela_DianaLupu Mirabela Diana Lupu_Mirabela_Diana Data 27 iunie 2026 20:59:23
Problema Infasuratoare convexa Scor 0
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    double x, y;
} Point;

Point H[240005];
Point P[120005];

int cmp(const void *a, const void *b) {
    Point *p1 = (Point *)a;
    Point *p2 = (Point *)b;

    if (p1->x < p2->x) return -1;
    if (p1->x > p2->x) return 1;
    if (p1->y < p2->y) return -1;
    if (p1->y > p2->y) return 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() {
    int N;
    scanf("%d", &N);

    for (int i = 0; i < N; i++)
        scanf("%lf %lf", &P[i].x, &P[i].y);

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

    int k = 0;

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

    // Upper hull
    int t = k + 1;
    for (int 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--; // ultimul punct este identic cu primul

    printf("%d\n", k);
    for (int i = 0; i < k; i++)
        printf("%.6lf %.6lf\n", H[i].x, H[i].y);

    return 0;
}