Cod sursa(job #3301101)

Utilizator Dragos_MatuDragos Gabriel Matu Dragos_Matu Data 21 iunie 2025 18:06:02
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 3.8 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct
{
    double x, y;
    int index;
} Point;

// Calculează produsul vectorial pentru trei puncte
// Returnează: > 0 pentru viraj la stânga, < 0 pentru viraj la dreapta, 0 pentru coliniaritate
double crossProduct(Point O, Point A, Point B)
{
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

// Calculează distanța pătrată între două puncte
double distanceSquared(Point a, Point b)
{
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

// Punctul de referință pentru sortare polară
Point pivot;

// Funcție de comparare pentru sortarea polară
int polarCompare(const void *a, const void *b)
{
    Point *pa = (Point *)a;
    Point *pb = (Point *)b;

    double cross = crossProduct(pivot, *pa, *pb);
    if (fabs(cross) < 1e-12)
    { // Puncte colineare
        // Sortează după distanță de la pivot
        double distA = distanceSquared(pivot, *pa);
        double distB = distanceSquared(pivot, *pb);
        if (distA < distB)
            return -1;
        if (distA > distB)
            return 1;
        return 0;
    }
    return (cross > 0) ? -1 : 1; // Sortare în sens trigonometric
}

// Schimbă două puncte
void swap(Point *a, Point *b)
{
    Point temp = *a;
    *a = *b;
    *b = temp;
}

int convexHull(Point *points, int n, Point *hull)
{
    if (n < 3)
    {
        for (int i = 0; i < n; i++)
        {
            hull[i] = points[i];
        }
        return n;
    }

    // Găsește punctul cu coordonata y minimă (și x minimă în caz de egalitate)
    int minIdx = 0;
    for (int i = 1; i < n; i++)
    {
        if (points[i].y < points[minIdx].y ||
            (fabs(points[i].y - points[minIdx].y) < 1e-12 && points[i].x < points[minIdx].x))
        {
            minIdx = i;
        }
    }

    // Mută punctul pivot la începutul vectorului
    swap(&points[0], &points[minIdx]);
    pivot = points[0];

    // Sortează punctele în ordine polară față de pivot
    qsort(points + 1, n - 1, sizeof(Point), polarCompare);

    // Elimină punctele colineare duplicate (păstrează cel mai îndepărtat)
    int m = 1;
    for (int i = 1; i < n; i++)
    {
        while (i < n - 1 && fabs(crossProduct(pivot, points[i], points[i + 1])) < 1e-12)
        {
            i++;
        }
        if (i < n)
        {
            points[m++] = points[i];
        }
    }

    if (m < 3)
        return 0;

    // Construiește înfășurătoarea convexă folosind Graham Scan
    hull[0] = points[0];
    hull[1] = points[1];
    hull[2] = points[2];
    int hullSize = 3;

    for (int i = 3; i < m; i++)
    {
        // Elimină punctele care fac viraj la dreapta
        while (hullSize > 1 && crossProduct(hull[hullSize - 2], hull[hullSize - 1], points[i]) < 1e-12)
        {
            hullSize--;
        }
        hull[hullSize++] = points[i];
    }

    return hullSize;
}

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

    if (!fin || !fout)
    {
        printf("Eroare la deschiderea fisierelor!\n");
        return 1;
    }

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

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

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

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

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

    fclose(fin);
    fclose(fout);

    free(points);
    free(hull);

    return 0;
}