Cod sursa(job #3300683)

Utilizator DavidFirizaFiriza David Valentin DavidFiriza Data 18 iunie 2025 15:52:50
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct { double x, y; } Point;

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

int cmp(const void *a, const void *b) {
    Point *u = (Point*)a;
    Point *v = (Point*)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 a, Point b, Point 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), 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 *in = fopen("infasuratoare.in", "r");
    FILE *out = fopen("infasuratoare.out", "w");
    
    int n;
    fscanf(in, "%d", &n);
    
    for (int i = 0; i < n; i++)
        fscanf(in, "%lf %lf", &p[i].x, &p[i].y);
    
    build(n);
    
    fprintf(out, "%d\n", k);
    for (int i = 0; i < k; i++)
        fprintf(out, "%.12lf %.12lf\n", h[i].x, h[i].y);
    
    fclose(in);
    fclose(out);
    return 0;
}