Pagini recente » Cod sursa (job #2597625) | Cod sursa (job #1449766)
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define NMAX 120000
struct point {
double x, y;
};
static struct point P[NMAX];
static int S[NMAX], n, start, top;
static int polar_cmp(const void *a, const void *b)
{
struct point p1 = *(const struct point *)a, p2 = *(const struct point *)b;
double dir = P[start].x * p1.y + p1.x * p2.y + P[start].y * p2.x -
p2.x * p1.y - p2.y * P[start].x - P[start].y * p1.x;
return dir > 0 ? 1 : -1;
}
static int is_ccw(int p1, int p2, int p3)
{
double dir = P[p1].x * P[p2].y + P[p2].x * P[p3].y + P[p1].y * P[p3].x -
P[p3].x * P[p2].y - P[p3].y * P[p1].x - P[p1].y * P[p2].x;
return (int) dir <= 0 ? 1 : 0;
}
int main(void)
{
struct point p;
double x, y, ymin = 1000000001.0;
int i;
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%lf %lf", &x, &y);
P[i].x = x;
P[i].y = y;
if (y < ymin)
start = i;
else if (fabs(y - ymin) <= 0.000000000001)
start = x < P[start].x ? i : start;
}
p = P[start];
P[start] = P[0];
P[0] = p;
qsort(&P[1], n - 1, sizeof(struct point), polar_cmp);
S[top++] = 0;
S[top++] = 1;
S[top++] = 2;
for (i = 3; i < n; i++) {
while (!is_ccw(S[top - 2], S[top - 1], i))
--top;
S[top++] = i;
}
printf("%d\n", top);
for (i = 0; i < top; i++)
printf("%lf %lf\n", P[S[i]].x, P[S[i]].y);
return 0;
}