Cod sursa(job #3358160)

Utilizator Lupu_Mirabela_DianaLupu Mirabela Diana Lupu_Mirabela_Diana Data 14 iunie 2026 23:04:59
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.74 kb
#include <stdio.h>
#include <stdlib.h>

#define NMAX 120000

typedef struct
{
    double x, y;
} Point;

Point p[NMAX], st[NMAX];
int n, top = 0;
Point start;

// cross product
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);
}

// distanta (nu neaparat necesara, dar ajuta la sortare stabila)
double dist(Point a, Point b)
{
    return (a.x - b.x) * (a.x - b.x)
         + (a.y - b.y) * (a.y - b.y);
}

// comparator pentru sortare polară
int cmp(const void *A, const void *B)
{
    Point *a = (Point *)A;
    Point *b = (Point *)B;

    double c = cross(start, *a, *b);

    if (c > 0) return -1;
    if (c < 0) return 1;

    // coliniare → sortăm după distanță
    double d1 = dist(start, *a);
    double d2 = dist(start, *b);

    if (d1 < d2) return -1;
    return 1;
}

int main()
{
    FILE *in, *out;

    in = fopen("infasuratoare.in", "r");
    out = fopen("infasuratoare.out", "w");

    fscanf(in, "%d", &n);

    for (int i = 0; i < n; i++)
    {
        fscanf(in, "%lf %lf", &p[i].x, &p[i].y);

        if (i == 0 ||
            p[i].x < start.x ||
            (p[i].x == start.x && p[i].y < start.y))
        {
            start = p[i];
        }
    }

    qsort(p, n, sizeof(Point), cmp);

    // construim hull
    for (int i = 0; i < n; i++)
    {
        while (top >= 2 &&
               cross(st[top - 2], st[top - 1], p[i]) <= 0)
        {
            top--;
        }

        st[top++] = p[i];
    }

    fprintf(out, "%d\n", top);

    for (int i = 0; i < top; i++)
    {
        fprintf(out, "%.6lf %.6lf\n", st[i].x, st[i].y);
    }

    fclose(in);
    fclose(out);

    return 0;
}