Pagini recente » Cod sursa (job #79187) | Cod sursa (job #2911241) | Cod sursa (job #79171) | Cod sursa (job #2187671) | Cod sursa (job #3301023)
#include <stdio.h>
#include <stdlib.h>
typedef struct {
double x, y;
} point_t;
point_t p[120000], h[120000];
int k;
int cmp(const void *a, const void *b) {
point_t *u = (point_t*)a;
point_t *v = (point_t*)b;
if (u->x < v->x)
return -1;
if (u->x > v->x)
return 1;
if (u->y < v->y)
return -1;
return 1;
}
double cross(point_t a, point_t b, point_t c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
void build(int n) {
qsort(p, n, sizeof(point_t), cmp);
k = 0;
for (int i = 0; i < n; i++) {
while (k >= 2 && cross(h[k-2], h[k-1], p[i]) <= 0)
k--;
h[k++] = p[i];
}
for (int i = n-2, t = k+1; i >= 0; i--) {
while (k >= t && cross(h[k-2], h[k-1], p[i]) <= 0)
k--;
h[k++] = p[i];
}
k--;
}
int main() {
FILE *input = fopen("infasuratoare.in", "r");
FILE *output = fopen("infasuratoare.out", "w");
int n;
fscanf(input, "%d", &n);
for (int i = 0; i < n; i++)
fscanf(input, "%lf %lf", &p[i].x, &p[i].y);
build(n);
fprintf(output, "%d\n", k);
for (int i = 0; i < k; i++)
fprintf(output, "%.12lf %.12lf\n", h[i].x, h[i].y);
fclose(input);
fclose(output);
return 0;
}