Pagini recente » Cod sursa (job #3358160) | Cod sursa (job #3358861) | Cod sursa (job #3358944) | Cod sursa (job #1320035) | Cod sursa (job #3358742)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define EPS 1e-9 // marja de eroare (numar foarte mic)
// punct 2D
typedef struct {
double x, y;
} Punct;
double produs_vectorial(Punct O, Punct A, Punct B)
{
return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
int comparare_puncte(const void *a, const void *b) // pentru qsort
{
Punct *p1 = (Punct *)a;
Punct *p2 = (Punct *)b;
if (fabs(p1->x - p2->x) > EPS) // sortez dupa coordonatele x
{
if (p1->x < p2->x) return -1;
else return 1;
}
if (fabs(p1->y - p2->y) > EPS) // daca coordonatele x sunt = sortez dupa y
{
if (p1->y < p2->y) return -1;
else return 1;
}
return 0;
}
int main()
{
FILE *fin = fopen("infasuratoare.in", "r");
FILE *fout = fopen("infasuratoare.out", "w");
int n;
if (fscanf(fin, "%d", &n) != 1) return 1;
Punct *P = (Punct *)malloc(n * sizeof(Punct));
for (int i = 0; i < n; i++)
{
fscanf(fin, "%lf %lf", &P[i].x, &P[i].y);
}
qsort(P, n, sizeof(Punct), comparare_puncte);
Punct *H = (Punct *)malloc(2 * n * sizeof(Punct));
int k = 0;
for (int i = 0; i < n; ++i)
{
while (k >= 2 && produs_vectorial(H[k - 2], H[k - 1], P[i]) <= EPS)
{
k--;
}
H[k++] = P[i];
}
int limita = k +1;
for (int i = n - 2; i >= 0; i--)
{
while (k>=limita && produs_vectorial(H[k-2], H[k-1], P[i]) <= EPS)
{
k--;
}
H[k++] = P[i];
}
k--;
fprintf(fout, "%d\n", k);
for (int i = 0; i < k; i++)
{
fprintf(fout, "%.6lf %.6lf\n", H[i].x, H[i].y);
}
free(P);
free(H);
fclose(fin);
fclose(fout);
return 0;
}