Cod sursa(job #3301135)

Utilizator robertcd29Chira Robert-Denis robertcd29 Data 21 iunie 2025 21:06:07
Problema Infasuratoare convexa Scor 0
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <stdio.h>
#include <stdlib.h>

typedef long long ll;
typedef struct { ll x, y; } P;

int cmpP(const void *a, const void *b) {
    P *p = (P*)a, *q = (P*)b;
    if (p->x < q->x) return -1;
    if (p->x > q->x) return 1;
    if (p->y < q->y) return -1;
    if (p->y > q->y) return 1;
    return 0;
}

ll cross(P a, P b, P c) {
    return (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);
}

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    P *a = malloc(n * sizeof(P));
    for (int i = 0; i < n; ++i) scanf("%lld %lld", &a[i].x, &a[i].y);
    qsort(a, n, sizeof(P), cmpP);
    P *hull = malloc(2 * n * sizeof(P));
    int m = 0;
    for (int i = 0; i < n; ++i) {
        while (m >= 2 && cross(hull[m-2], hull[m-1], a[i]) <= 0) m--;
        hull[m++] = a[i];
    }
    int t = m;
    for (int i = n-2; i >= 0; --i) {
        while (m > t && cross(hull[m-2], hull[m-1], a[i]) <= 0) m--;
        hull[m++] = a[i];
    }
    if (n > 1) m--;
    printf("%d\n", m);
    for (int i = 0; i < m; ++i)
        printf("%lld %lld\n", hull[i].x, hull[i].y);
    return 0;
}