Pagini recente » Cod sursa (job #3325825) | Cod sursa (job #3358166) | Cod sursa (job #3358283) | Cod sursa (job #3358170) | Cod sursa (job #3359355)
#include <stdio.h>
#include <stdlib.h>
// ALlgo lui Andrew?
#define eps 1e-9 // TOL pentru flt
typedef struct
{
double x, y;
} Punct;
Punct puncte[120005];
Punct stiva[240005];
int compara(const void *a, const void *b)
{
Punct *p1 = (Punct *)a;
Punct *p2 = (Punct *)b;
if (p1->x < p2->x - eps)
return -1;
if (p1->x > p2->x + eps)
return 1;
if (p1->y < p2->y - eps)
return -1;
if (p1->y > p2->y + eps)
return 1;
return 0;
}
double produs(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");
int n, i, k = 0, t;
fscanf(fin, "%d", &n);
for (i = 0; i < n; i++)
{
fscanf(fin, "%lf %lf", &puncte[i].x, &puncte[i].y);
}
qsort(puncte, n, sizeof(Punct), compara);
for (i = 0; i < n; i++)
{
while (k >= 2 && produs(stiva[k - 2], stiva[k - 1], puncte[i]) <= eps)
{
k--;
}
stiva[k++] = puncte[i];
}
t = k + 1;
for (i = n - 2; i >= 0; i--)
{
while (k >= t && produs(stiva[k - 2], stiva[k - 1], puncte[i]) <= eps)
{
k--;
}
stiva[k++] = puncte[i];
}
k--;
fprintf(fout, "%d\n", k);
for (i = 0; i < k; i++)
{
fprintf(fout, "%.6lf %.6lf\n", stiva[i].x, stiva[i].y);
}
fclose(fin);
fclose(fout);
return 0;
}