Pagini recente » ..::Hyper Kid Designer Profile::.. | Cod sursa (job #1260912) | Cod sursa (job #1260918) | Borderou de evaluare (job #1322634) | Cod sursa (job #3358681)
#include <stdio.h>
#include <stdlib.h>
typedef struct
{
double x;
double y;
} punct;
punct puncte[120005];
punct infasuratoare[240005];
double determinant(punct a, punct b, punct c)
{
return (b.x - a.x) * (c.y - a.y)
- (b.y - a.y) * (c.x - a.x);
}
int compara(const void *a, const void *b)
{
punct p1 = *(punct *)a;
punct p2 = *(punct *)b;
if (p1.x < p2.x)
{
return -1;
}
if (p1.x > p2.x)
{
return 1;
}
if (p1.y < p2.y)
{
return -1;
}
if (p1.y > p2.y)
{
return 1;
}
return 0;
}
int main()
{
FILE *fin = fopen("infasuratoare.in", "r");
FILE *fout = fopen("infasuratoare.out", "w");
int n;
fscanf(fin, "%d", &n);
for (int i = 0; i < n; i++)
{
fscanf(fin, "%lf %lf", &puncte[i].x, &puncte[i].y);
}
qsort(puncte, n, sizeof(punct), compara);
int nr_puncte = 0;
for (int i = 0; i < n; i++)
{
while (nr_puncte >= 2 &&
determinant(infasuratoare[nr_puncte - 2], infasuratoare[nr_puncte - 1], puncte[i]) <= 0)
{
nr_puncte--;
}
infasuratoare[nr_puncte++] = puncte[i];
}
int inceput_parte_superioara = nr_puncte + 1;
for (int i = n - 2; i >= 0; i--)
{
while (nr_puncte >= inceput_parte_superioara && determinant(infasuratoare[nr_puncte - 2], infasuratoare[nr_puncte - 1], puncte[i]) <= 0)
{
nr_puncte--;
}
infasuratoare[nr_puncte++] = puncte[i];
}
nr_puncte--;
fprintf(fout, "%d\n", nr_puncte);
for (int i = 0; i < nr_puncte; i++)
{
fprintf(fout, "%.6f %.6f\n", infasuratoare[i].x, infasuratoare[i].y);
}
fclose(fin);
fclose(fout);
return 0;
}