Pagini recente » Cod sursa (job #2498672) | Cod sursa (job #2750555) | Cod sursa (job #3003629) | Cod sursa (job #2498666) | Cod sursa (job #3300683)
#include <stdio.h>
#include <stdlib.h>
typedef struct { double x, y; } Point;
Point p[120000], h[120000];
int k;
int cmp(const void *a, const void *b) {
Point *u = (Point*)a;
Point *v = (Point*)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 a, Point b, Point 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), 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 *in = fopen("infasuratoare.in", "r");
FILE *out = fopen("infasuratoare.out", "w");
int n;
fscanf(in, "%d", &n);
for (int i = 0; i < n; i++)
fscanf(in, "%lf %lf", &p[i].x, &p[i].y);
build(n);
fprintf(out, "%d\n", k);
for (int i = 0; i < k; i++)
fprintf(out, "%.12lf %.12lf\n", h[i].x, h[i].y);
fclose(in);
fclose(out);
return 0;
}