Cod sursa(job #3359351)

Utilizator NeamtuFelixNeamtu Felix NeamtuFelix Data 27 iunie 2026 12:19:36
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 2.24 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct {
    double x, y;
} Punct;

Punct pivot; /* punctul de referinta pentru sortarea unghiulara */

double cross(Punct O, Punct A, Punct B) {
    return (A.x - O.x) * (B.y - O.y)
         - (A.y - O.y) * (B.x - O.x);
}

double dist2(Punct a, Punct b) {
    double dx = a.x - b.x, dy = a.y - b.y;
    return dx*dx + dy*dy;
}

int cmp_unghi(const void* a, const void* b) {
    Punct* p = (Punct*)a;
    Punct* q = (Punct*)b;
    double cr = cross(pivot, *p, *q);
    if (cr > 1e-12) return -1;   /* p e mai "la stanga" = vine primul in anti-orar */
    if (cr < -1e-12) return  1;
    /* coliniari: cel mai aproape de pivot vine primul */
    double dp = dist2(pivot, *p);
    double dq = dist2(pivot, *q);
    if (dp < dq) return -1;
    if (dp > dq) return  1;
    return 0;
}

int main() {
    FILE* fin  = fopen("infasuratoare.in",  "r");
    FILE* fout = fopen("infasuratoare.out", "w");

    int n;
    fscanf(fin, "%d", &n);

    Punct* pts = (Punct*)malloc(n * sizeof(Punct));
    for (int i = 0; i < n; i++)
        fscanf(fin, "%lf %lf", &pts[i].x, &pts[i].y);

    /* Gasim pivotul: y minim, la egalitate x minim */
    int idx = 0;
    for (int i = 1; i < n; i++) {
        if (pts[i].y < pts[idx].y ||
           (pts[i].y == pts[idx].y && pts[i].x < pts[idx].x))
            idx = i;
    }
    /* Punem pivotul pe pozitia 0 */
    Punct tmp = pts[0]; pts[0] = pts[idx]; pts[idx] = tmp;
    pivot = pts[0];

    /* Sortam restul punctelor dupa unghi polar fata de pivot */
    qsort(pts + 1, n - 1, sizeof(Punct), cmp_unghi);

    /* Graham Scan */
    Punct* stiva = (Punct*)malloc(n * sizeof(Punct));
    int top = 0;
    stiva[top++] = pts[0];
    stiva[top++] = pts[1];

    for (int i = 2; i < n; i++) {
        while (top >= 2 && cross(stiva[top-2], stiva[top-1], pts[i]) <= 0)
            top--;
        stiva[top++] = pts[i];
    }

    /* Stiva contine hull-ul in ordine trigonometrica, starting din pivot */
    fprintf(fout, "%d\n", top);
    for (int i = 0; i < top; i++)
        fprintf(fout, "%.6f %.6f\n", stiva[i].x, stiva[i].y);

    free(pts);
    free(stiva);
    fclose(fin);
    fclose(fout);
    return 0;
}