Pagini recente » Cod sursa (job #162876) | Cod sursa (job #3176892) | Cod sursa (job #713041) | Cod sursa (job #162692) | Cod sursa (job #3232956)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define in "infasuratoare.in"
#define out "infasuratoare.out"
typedef struct
{
double x;
double y;
} Punct;
double produsVectorial(Punct A, Punct B, Punct C)
{
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
double distanta(Punct A, Punct B)
{
return sqrt((B.x - A.x) * (B.x - A.x) + (B.y - A.y) * (B.y - A.y));
}
int compara(const void *a, const void *b)
{
Punct A = *((Punct *)a);
Punct B = *((Punct *)b);
double unghiA = atan2(A.y, A.x);
double unghiB = atan2(B.y, B.x);
if (unghiA < unghiB)
return -1;
if (unghiA > unghiB)
return 1;
return 0;
}
void acoperireConvexa(Punct P[], int n, FILE *fout)
{
if (n < 3)
return;
int minIdx = 0;
for (int i = 1; i < n; i++)
{
if (P[i].y < P[minIdx].y || (P[i].y == P[minIdx].y && P[i].x < P[minIdx].x))
{
minIdx = i;
}
}
Punct temp = P[0];
P[0] = P[minIdx];
P[minIdx] = temp;
qsort(&P[1], n - 1, sizeof(Punct), compara);
Punct *stiva = (Punct *)malloc(n * sizeof(Punct));
int top = 2;
stiva[0] = P[0];
stiva[1] = P[1];
stiva[2] = P[2];
for (int i = 3; i < n; i++)
{
while (produsVectorial(stiva[top - 1], stiva[top], P[i]) <= 0)
{
top--;
}
top++;
stiva[top] = P[i];
}
fprintf(fout, "%d\n", top + 1);
for (int i = 0; i <= top; i++)
{
fprintf(fout, "%lf %lf\n", stiva[i].x, stiva[i].y);
}
free(stiva);
}
int main()
{
FILE *fin, *fout;
fin = fopen(in, "r");
fout = fopen(out, "w");
int N, i;
fscanf(fin, "%d", &N);
Punct P[N];
for (i = 0; i < N; i++)
{
fscanf(fin, "%lf %lf", &P[i].x, &P[i].y);
}
acoperireConvexa(P, N, fout);
fclose(fin);
fclose(fout);
return 0;
}