Cod sursa(job #3359330)

Utilizator barsescu_andreiBarsescu Andrei Mircea barsescu_andrei Data 27 iunie 2026 03:05:04
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <stdio.h>
#include <stdlib.h>

#define MAXN 120005

typedef struct {
    long double x, y;
} Point;

int n, stack_size;
Point points[MAXN], stack[MAXN];
Point origin;

long 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 cmp_by_angle(const void *a, const void *b) {
    Point *A = (Point *)a;
    Point *B = (Point *)b;
    long double cr = cross(origin, *A, *B);
    if (cr != 0) return (cr > 0) ? -1 : 1;
    long double dist_A = (A->x - origin.x)*(A->x - origin.x) + (A->y - origin.y)*(A->y - origin.y);
    long double dist_B = (B->x - origin.x)*(B->x - origin.x) + (B->y - origin.y)*(B->y - origin.y);
    return (dist_A < dist_B) ? -1 : 1;
}

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

    fscanf(fin, "%d", &n);
    for (int i = 0; i < n; i++)
        fscanf(fin, "%Lf %Lf", &points[i].x, &points[i].y);

    int origin_idx = 0;
    for (int i = 1; i < n; i++)
        if (points[i].x < points[origin_idx].x ||
           (points[i].x == points[origin_idx].x && points[i].y < points[origin_idx].y))
            origin_idx = i;

    Point tmp = points[0]; points[0] = points[origin_idx]; points[origin_idx] = tmp;
    origin = points[0];

    qsort(points + 1, n - 1, sizeof(Point), cmp_by_angle);

    stack[0] = points[0];
    stack[1] = points[1];
    stack_size = 2;

    for (int i = 2; i < n; i++) {
        while (stack_size >= 2 && cross(stack[stack_size-2], stack[stack_size-1], points[i]) <= 0)
            stack_size--;
        stack[stack_size++] = points[i];
    }

    fprintf(fout, "%d\n", stack_size);
    for (int i = 0; i < stack_size; i++)
        fprintf(fout, "%.6Lf %.6Lf\n", stack[i].x, stack[i].y);

    fclose(fin);
    fclose(fout);
}