Pagini recente » Borderou de evaluare (job #1322634) | Cod sursa (job #3358681) | Borderou de evaluare (job #1322619) | Cod sursa (job #3357104) | Cod sursa (job #3358160)
#include <stdio.h>
#include <stdlib.h>
#define NMAX 120000
typedef struct
{
double x, y;
} Point;
Point p[NMAX], st[NMAX];
int n, top = 0;
Point start;
// cross product
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);
}
// distanta (nu neaparat necesara, dar ajuta la sortare stabila)
double dist(Point a, Point b)
{
return (a.x - b.x) * (a.x - b.x)
+ (a.y - b.y) * (a.y - b.y);
}
// comparator pentru sortare polară
int cmp(const void *A, const void *B)
{
Point *a = (Point *)A;
Point *b = (Point *)B;
double c = cross(start, *a, *b);
if (c > 0) return -1;
if (c < 0) return 1;
// coliniare → sortăm după distanță
double d1 = dist(start, *a);
double d2 = dist(start, *b);
if (d1 < d2) return -1;
return 1;
}
int main()
{
FILE *in, *out;
in = fopen("infasuratoare.in", "r");
out = fopen("infasuratoare.out", "w");
fscanf(in, "%d", &n);
for (int i = 0; i < n; i++)
{
fscanf(in, "%lf %lf", &p[i].x, &p[i].y);
if (i == 0 ||
p[i].x < start.x ||
(p[i].x == start.x && p[i].y < start.y))
{
start = p[i];
}
}
qsort(p, n, sizeof(Point), cmp);
// construim hull
for (int i = 0; i < n; i++)
{
while (top >= 2 &&
cross(st[top - 2], st[top - 1], p[i]) <= 0)
{
top--;
}
st[top++] = p[i];
}
fprintf(out, "%d\n", top);
for (int i = 0; i < top; i++)
{
fprintf(out, "%.6lf %.6lf\n", st[i].x, st[i].y);
}
fclose(in);
fclose(out);
return 0;
}