Cod sursa(job #3300062)

Utilizator blnsara_10Sara Balanescu blnsara_10 Data 12 iunie 2025 15:32:29
Problema Infasuratoare convexa Scor 20
Compilator c-64 Status done
Runda Arhiva educationala Marime 2.89 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

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;
}

void sort(Point *points, int start, int end) {
    for (int i = start; i < end; i++) {
        for (int j = i + 1; j < end; j++) {
            double cross = produsVectorial(pivot, points[i], points[j]);
            int swap = 0;

            if (fabs(cross) < 0.0000001) {
                double d1 = distanta(pivot, points[i]);
                double d2 = distanta(pivot, points[j]);
                if (d1 > d2) swap = 1;
            } else if (cross < 0) {
                swap = 1;
            }

            if (swap) {
                Point temp = points[i];
                points[i] = points[j];
                points[j] = temp;
            }
        }
    }
}

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];

    sort(points, 1, n);

    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;
}