Cod sursa(job #3301023)

Utilizator RobertMM05Molcomis Robert-Marian RobertMM05 Data 20 iunie 2025 21:25:30
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    double x, y;
} point_t;

point_t p[120000], h[120000];
int k;

int cmp(const void *a, const void *b) {
    point_t *u = (point_t*)a;
    point_t *v = (point_t*)b;
    if (u->x < v->x)
        return -1;
    if (u->x > v->x)
        return 1;
    if (u->y < v->y)
        return -1;
    return 1;
}

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

void build(int n) {
    qsort(p, n, sizeof(point_t), cmp);
    k = 0;
    
    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];
    }
    
    for (int i = n-2, t = k+1; i >= 0; i--) {
        while (k >= t && cross(h[k-2], h[k-1], p[i]) <= 0)
            k--;
        h[k++] = p[i];
    }
    
    k--;
}

int main() {
    FILE *input = fopen("infasuratoare.in", "r");
    FILE *output = fopen("infasuratoare.out", "w");
    
    int n;
    fscanf(input, "%d", &n);
    
    for (int i = 0; i < n; i++)
        fscanf(input, "%lf %lf", &p[i].x, &p[i].y);
    
    build(n);
    
    fprintf(output, "%d\n", k);
    for (int i = 0; i < k; i++)
        fprintf(output, "%.12lf %.12lf\n", h[i].x, h[i].y);
    
    fclose(input);
    fclose(output);
    return 0;
}