Pagini recente » Monitorul de evaluare | Cod sursa (job #3359414) | Cod sursa (job #3359330)
#include <stdio.h>
#include <stdlib.h>
#define MAXN 120005
typedef struct {
long double x, y;
} Point;
int n, stack_size;
Point points[MAXN], stack[MAXN];
Point origin;
long double cross(Point O, Point A, Point B) {
return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
int cmp_by_angle(const void *a, const void *b) {
Point *A = (Point *)a;
Point *B = (Point *)b;
long double cr = cross(origin, *A, *B);
if (cr != 0) return (cr > 0) ? -1 : 1;
long double dist_A = (A->x - origin.x)*(A->x - origin.x) + (A->y - origin.y)*(A->y - origin.y);
long double dist_B = (B->x - origin.x)*(B->x - origin.x) + (B->y - origin.y)*(B->y - origin.y);
return (dist_A < dist_B) ? -1 : 1;
}
int main() {
FILE *fin = fopen("infasuratoare.in", "r");
FILE *fout = fopen("infasuratoare.out", "w");
fscanf(fin, "%d", &n);
for (int i = 0; i < n; i++)
fscanf(fin, "%Lf %Lf", &points[i].x, &points[i].y);
int origin_idx = 0;
for (int i = 1; i < n; i++)
if (points[i].x < points[origin_idx].x ||
(points[i].x == points[origin_idx].x && points[i].y < points[origin_idx].y))
origin_idx = i;
Point tmp = points[0]; points[0] = points[origin_idx]; points[origin_idx] = tmp;
origin = points[0];
qsort(points + 1, n - 1, sizeof(Point), cmp_by_angle);
stack[0] = points[0];
stack[1] = points[1];
stack_size = 2;
for (int i = 2; i < n; i++) {
while (stack_size >= 2 && cross(stack[stack_size-2], stack[stack_size-1], points[i]) <= 0)
stack_size--;
stack[stack_size++] = points[i];
}
fprintf(fout, "%d\n", stack_size);
for (int i = 0; i < stack_size; i++)
fprintf(fout, "%.6Lf %.6Lf\n", stack[i].x, stack[i].y);
fclose(fin);
fclose(fout);
}