Cod sursa(job #3359384)

Utilizator alexandru.simoneaSimonea Alexandru alexandru.simonea Data 27 iunie 2026 16:31:48
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <stdio.h>
#include <stdlib.h>

#define MAXN 120005

typedef struct {
    double x, y;
} Point;

Point pts[MAXN], hull[2 * MAXN];

int cmp(const void *a, const void *b)
{
    Point *p1 = (Point *)a;
    Point *p2 = (Point *)b;

    if (p1->x < p2->x) return -1;
    if (p1->x > p2->x) return 1;
    if (p1->y < p2->y) return -1;
    if (p1->y > p2->y) return 1;

    return 0;
}

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 *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", &pts[i].x, &pts[i].y);

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

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


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

    k--;

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

    for (int i = 0; i < k; i++)
        fprintf(out, "%.10lf %.10lf\n", hull[i].x, hull[i].y);

    fclose(in);
    fclose(out);

    return 0;
}