Pagini recente » Cod sursa (job #436341) | Cod sursa (job #1748651) | Cod sursa (job #1510443) | Cod sursa (job #3297912) | Cod sursa (job #3300901)
#include <stdio.h>
#include <stdlib.h>
typedef struct {
double x, y;
} punct;
int ordonare_puncte(const void *a, const void *b)
{
punct *p = (punct*) a;
punct *q = (punct*) b;
if(p->x < q->x)
return -1;
else if(p->x > q->x)
return 1;
else
{
if(p->y < q->y)
return -1;
else
return 1;
}
return 0;
}
double pvect(punct O, punct A, punct B)
{
return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
int main()
{
FILE *fin = fopen("infasuratoare.in", "r");
FILE *fout = fopen("infasuratoare.out", "w");
if(!fin || !fout)
{
printf("nu s-a putut deschide un fisier!\n");
return 1;
}
int N;
fscanf(fin, "%d", &N);
punct *puncte = malloc(N * sizeof(punct));
for (int i = 0; i < N; i++)
fscanf(fin, "%lf %lf", &puncte[i].x, &puncte[i].y);
qsort(puncte, N, sizeof(punct), ordonare_puncte);
punct *stiva = malloc(2 * N * sizeof(punct));
int top = 0;
for(int i = 0; i < N; i++)
{
while(top >= 2 && pvect(stiva[top-2], stiva[top-1], puncte[i]) <= 0)
top--;
stiva[top++] = puncte[i];
}
int dmax = top;
for(int i = N - 2; i >= 0; i--)
{
while (top >= dmax + 1 && pvect(stiva[top-2], stiva[top-1], puncte[i]) <= 0)
top--;
stiva[top++] = puncte[i];
}
top--;
fprintf(fout, "%d\n", top);
for(int i = 0; i < top; i++)
fprintf(fout, "%.6lf %.6lf\n", stiva[i].x, stiva[i].y);
free(puncte);
free(stiva);
fclose(fin);
fclose(fout);
return 0;
}