Cod sursa(job #3358912)

Utilizator serban-andrei.cristeaCristea Serban-Andrei serban-andrei.cristea Data 21 iunie 2026 22:00:48
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    double x, y;
} Point;

int cmp(const void *a, const void *b) {
    Point *p1 = (Point *)a;
    Point *p2 = (Point *)b;
    if (p1->x != p2->x) return (p1->x < p2->x) ? -1 : 1;
    return (p1->y < p2->y) ? -1 : 1;
}

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() {
    FILE *fin = fopen("infasuratoare.in", "r");
    FILE *fout = fopen("infasuratoare.out", "w");
    int n;
    fscanf(fin, "%d", &n);
    Point *p = (Point*)malloc(n * sizeof(Point));
    for (int i = 0; i < n; i++) {
        fscanf(fin, "%lf %lf", &p[i].x, &p[i].y);
    }
    
    qsort(p, n, sizeof(Point), cmp);
    
    Point *h = (Point*)malloc(2 * n * sizeof(Point));
    int 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 start = 0;
    for(int i = 1; i < k; i++) {
        if(h[i].y < h[start].y || (h[i].y == h[start].y && h[i].x < h[start].x)) {
            start = i;
        }
    }
    
    fprintf(fout, "%d\n", k);
    for (int i = 0; i < k; i++) {
        int idx = (start + i) % k;
        fprintf(fout, "%.6lf %.6lf\n", h[idx].x, h[idx].y);
    }
    
    fclose(fin);
    fclose(fout);
    free(p);
    free(h);
    return 0;
}