Pagini recente » Cod sursa (job #2204854) | Cod sursa (job #2429771) | Cod sursa (job #1063735) | Cod sursa (job #284003) | Cod sursa (job #1276527)
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct
{
double x;
double y;
} Punct;
FILE *in;
FILE *out;
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)
{
fprintf (out, "%.6lf %.6lf\n", p.x, p.y);
}
Punct* cautareBinara (int stanga, int dreapta, Punct punctCurent)
{
int mijloc = (stanga + dreapta) >> 1;
if (punctCurent.x == acoperireConvexa[mijloc][0].x)
{
if (punctCurent.y == acoperireConvexa[mijloc][0].y)
return acoperireConvexa[mijloc];
else if (punctCurent.y < acoperireConvexa[mijloc][0].y)
return cautareBinara (stanga, mijloc - 1, punctCurent);
else
return cautareBinara (mijloc + 1, dreapta, punctCurent);
}
if (punctCurent.x < acoperireConvexa[mijloc][0].x)
return cautareBinara (stanga, mijloc - 1, punctCurent);
else
return cautareBinara (mijloc + 1, dreapta, punctCurent);
}
int compare (const void *a, const void *b)
{
const Punct *m1 = a;
const Punct *m2 = b;
if (m1[0].x == m2[0].x)
{
if (m1[0].y == m2[0].y)
return 0;
if (m1[0].y < m2[0].y)
return -1;
else
return 1;
}
if (m1[0].x < m2[0].x)
return -1;
else
return 1;
}
int main ()
{
in = fopen ("infasuratoare.in", "r");
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;
}
}
fprintf (out, "%d\n", idx);
Punct dummy[1][2];
qsort (acoperireConvexa, idx, sizeof (dummy), &compare);
printPunct (acoperireConvexa[0][0]);
Punct punctCurent = acoperireConvexa[0][1];
int diff = 1;
while (diff < idx) {
Punct *next = cautareBinara (0, idx, punctCurent);
printPunct (next[0]);
punctCurent = next[1];
diff++;
}
fclose (in);
fclose (out);
return 0;
}