Cod sursa(job #3300067)

Utilizator blnsara_10Sara Balanescu blnsara_10 Data 12 iunie 2025 15:40:19
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 2.72 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
//https://infoarena.ro/problema/infasuratoare
#define MAXIM 120000

typedef struct {
    double x, y;
} Point;

Point pivot;

double produsVectorial(Point a, Point b, Point c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

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

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

    double cross = produsVectorial(pivot, *p1, *p2);

    if (fabs(cross) <0.0000001) {
        double d1 = distanta(pivot, *p1);
        double d2 = distanta(pivot, *p2);
        if (d1 < d2) return -1;
        if (d1 > d2) return 1;
        return 0;
    }

    if (cross > 0) return -1;
    return 1;
}

int gasesteBaza(Point *points, int n) {
    int min = 0;
    for (int i = 1; i < n; i++) {
        if (points[i].y < points[min].y) {
            min = i;
        } else if (fabs(points[i].y - points[min].y) < 0.0000001 && points[i].x < points[min].x) {
            min = i;
        }
    }
    return min;
}

void interschimba(Point *a, Point *b) {
    Point temp = *a;
    *a = *b;
    *b = temp;
}

int construiestePoligon(Point *points, int n, Point *hull) {
    if (n < 3) return 0;

    int minPos = gasesteBaza(points, n);
    interschimba(&points[0], &points[minPos]);
    pivot = points[0];

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

    int size = 0;
    hull[size++] = points[0];
    hull[size++] = points[1];

    for (int i = 2; i < n; i++) {
        while (size > 1) {
            double cross = produsVectorial(hull[size-2], hull[size-1], points[i]);
            if (cross <= 0.0000001) {
                size--;
            } else {
                break;
            }
        }
        hull[size++] = points[i];
    }

    return size;
}

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

    if (!in || !out)
        return -1;

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

    Point *points = malloc(n * sizeof(Point));
    Point *hull = malloc(n * sizeof(Point));

    if (!points || !hull) {
        fclose(in);
        fclose(out);
        return -1;
    }

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

    int hullSize = construiestePoligon(points, n, hull);

    fprintf(out, "%d\n", hullSize);
    for (int i = 0; i < hullSize; i++) {
        fprintf(out, "%.6f %.6f\n", hull[i].x, hull[i].y);
    }

    free(points);
    free(hull);
    fclose(in);
    fclose(out);
    return 0;
}