Pagini recente » Cod sursa (job #2268080) | Cod sursa (job #982915) | Cod sursa (job #3196799) | Cod sursa (job #524377) | Cod sursa (job #1276482)
#include <stdio.h>
#include <assert.h>
typedef struct
{
double x;
double y;
} Punct;
Punct setPuncte[120000];
Punct acoperireConvexa[120000][2];
int testOrientare (Punct p, Punct q, Punct r)
{
int x1 = p.x; int x2 = q.x; int x3 = r.x;
int y1 = p.y; int y2 = q.y; int y3 = r.y;
return ((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1));
}
void printPunct (Punct p)
{
printf ("%.6lf %.6lf\n", p.x, p.y);
}
int main ()
{
FILE *in = fopen ("infasuratoare.in", "r");
FILE *out = fopen ("infasuratoare.out", "w");
int n;
assert (fscanf (in, "%d", &n) == 1);
int i, j, k;
for (i = 0; i < n; ++i)
assert (fscanf (in, "%lf%lf", &setPuncte[i].x, &setPuncte[i].y) == 2);
int valid; int idx = 0;
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
{
if (i == j) continue;
valid = 1;
for (k = 0; k < n; ++k)
if (i != k && j != k &&
testOrientare (setPuncte[i], setPuncte[j], setPuncte[k]) < 0)
{
valid = 0;
break;
}
if (valid == 1)
{
acoperireConvexa [idx][0] = setPuncte[i];
acoperireConvexa [idx][1] = setPuncte[j];
++idx;
}
}
printf ("%d\n", idx);
printPunct (acoperireConvexa[0][0]);
Punct punctCurent = acoperireConvexa[0][1];
int diff = 1;
while (diff < idx) {
for (i = 0; i < idx; ++i)
{
if (acoperireConvexa[i][0].x == punctCurent.x &&
acoperireConvexa[i][0].y == punctCurent.y)
{
printPunct (acoperireConvexa [i][0]);
punctCurent = acoperireConvexa [i][1];
diff++;
break;
}
}
}
fclose (in);
fclose (out);
return 0;
}