Pagini recente » Cod sursa (job #1762869) | Autentificare | Cod sursa (job #717844) | Cod sursa (job #1033040) | Cod sursa (job #1277151)
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <math.h>
typedef struct
{
double x;
double y;
} Point;
const double EPS = 0.000000000001;
int testOrientare (Point p, Point q, Point r)
{
double x1 = p.x; double x2 = q.x; double x3 = r.x;
double y1 = p.y; double y2 = q.y; double y3 = r.y;
return ((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1));
}
Point setPoints[120000];
Point Lupper [120000];
Point Llower [120000];
FILE *in;
FILE *out;
int compare (const void *a, const void *b)
{
Point p = *(Point *) a;
Point q = *(Point *) b;
if (fabs(p.x - q.x) < EPS)
{
if (fabs(p.y - q.y) < EPS)
return 0;
else if (p.y < q.y)
return -1;
else
return 1;
}
if (p.x < q.x)
return -1;
else
return 1;
}
void printPoint (Point p)
{
fprintf (out, "%.12lf %.12lf\n", p.x, p.y);
}
int main()
{
in = fopen ("infasuratoare.in", "r");
out = fopen ("infasuratoare.out", "w");
int n;
assert (fscanf (in, "%d", &n) == 1);
int i;
for (i = 0; i < n; ++i)
assert (fscanf (in, "%lf%lf", &setPoints[i].x, &setPoints[i].y) == 2);
qsort (setPoints, n, sizeof (Point), &compare);
Lupper [0] = setPoints[0];
Lupper [1] = setPoints[1];
int uk = 2;
for (i = 2; i < n; ++i)
{
Lupper [uk] = setPoints[i];
while (uk >= 2 && testOrientare (Lupper[uk - 2], Lupper[uk - 1], Lupper[uk]) > EPS)
{
Lupper [uk - 1] = Lupper [uk];
uk--;
}
uk++;
}
Llower [0] = setPoints[n - 1];
Llower [1] = setPoints[n - 2];
int lk = 2;
for (i = n - 3; i >= 0; --i)
{
Llower [lk] = setPoints[i];
while (lk >= 2 && testOrientare (Llower [lk - 2], Llower[lk - 1], Llower [lk]) > EPS)
{
Llower [lk - 1] = Llower [lk];
lk--;
}
lk++;
}
fprintf (out, "%d\n", lk + uk - 2);
for (i = uk - 1; i >= 0; --i)
printPoint (Lupper[i]);
for (i = lk - 2; i >= 1; --i)
printPoint (Llower[i]);
return 0;
}