Pagini recente » Cod sursa (job #628256) | Cod sursa (job #352162) | Cod sursa (job #1362671) | Cod sursa (job #577009) | Cod sursa (job #3301101)
#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;
}