Cod sursa(job #3301020)

Utilizator CosminM12Murariu Rusalin - Cosmin CosminM12 Data 20 iunie 2025 20:21:33
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.85 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct {
    double x, y;
} Point_t;

int comparePoints(const void *a, const void *b) {
    Point_t *p1 = (Point_t *)a;
    Point_t *p2 = (Point_t *)b;

    if(p1->x != p2->x) {
        return (p1->x < p2->x) ? -1 : 1;
    }
    if(p1->y != p2->y) {
        return (p1->y < p2->y) ? -1 : 1;
    }

    return 0;
}

double checkDirection(Point_t a, Point_t b, Point_t c) { //Cross product (>0 = left; 0 = collinear; <0 = right)
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

int findShape(Point_t *points, int n, Point_t **finalShape) {
    qsort(points, n, sizeof(Point_t), comparePoints); //Sort points with respect to x and then, after y

    Point_t *shape = (Point_t *)malloc(2*n*sizeof(Point_t));
    int k = 0;

    //Lower shape
    for(int i=0;i<n;i++) {
        while(k >= 2 && checkDirection(shape[k-2], shape[k-1], points[i]) <= 0) {
            k--;
        }
        shape[k++] = points[i];
    }

    //Upper shape
    int t = k+1;
    for(int i=n-2;i>-1;i--) {
        while(k >= t && checkDirection(shape[k-2], shape[k-1], points[i]) <= 0) {
            k--;
        }
        shape[k++] = points[i];
    }

    k--;
    *finalShape = shape;

    return k; //Shape size
}

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

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

    Point_t *points = (Point_t *)malloc(n*sizeof(Point_t));
    Point_t *shape;

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

    int k = findShape(points, n, &shape);

    fprintf(output, "%d\n", k);
    for(int i=0;i<k;i++) {
        fprintf(output, "%.6lf %.6lf\n", shape[i].x, shape[i].y);
    }

    free(points);
    free(shape);

    fclose(input);
    fclose(output);
    return 0;
}