Pagini recente » Cod sursa (job #306349) | Cod sursa (job #3286276) | Cod sursa (job #214107) | Cod sursa (job #3294655) | Cod sursa (job #3300062)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct {
double x, y;
} Point;
Point pivot;
double produsVectorial(Point a, Point b, Point c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
double distanta(Point a, Point b) {
double dx = a.x - b.x;
double dy = a.y - b.y;
return dx * dx + dy * dy;
}
void sort(Point *points, int start, int end) {
for (int i = start; i < end; i++) {
for (int j = i + 1; j < end; j++) {
double cross = produsVectorial(pivot, points[i], points[j]);
int swap = 0;
if (fabs(cross) < 0.0000001) {
double d1 = distanta(pivot, points[i]);
double d2 = distanta(pivot, points[j]);
if (d1 > d2) swap = 1;
} else if (cross < 0) {
swap = 1;
}
if (swap) {
Point temp = points[i];
points[i] = points[j];
points[j] = temp;
}
}
}
}
int gasesteBaza(Point *points, int n) {
int min = 0;
for (int i = 1; i < n; i++) {
if (points[i].y < points[min].y) {
min = i;
} else if (fabs(points[i].y - points[min].y) < 0.0000001 && points[i].x < points[min].x) {
min = i;
}
}
return min;
}
void interschimba(Point *a, Point *b) {
Point temp = *a;
*a = *b;
*b = temp;
}
int construiestePoligon(Point *points, int n, Point *hull) {
if (n < 3) return 0;
int minPos = gasesteBaza(points, n);
interschimba(&points[0], &points[minPos]);
pivot = points[0];
sort(points, 1, n);
int size = 0;
hull[size++] = points[0];
hull[size++] = points[1];
for (int i = 2; i < n; i++) {
while (size > 1) {
double cross = produsVectorial(hull[size-2], hull[size-1], points[i]);
if (cross <= 0.0000001) {
size--;
} else {
break;
}
}
hull[size++] = points[i];
}
return size;
}
int main() {
FILE *in = fopen("infasuratoare.in", "r");
FILE *out = fopen("infasuratoare.out", "w");
if (!in || !out)
return -1;
int n;
fscanf(in, "%d", &n);
Point *points = malloc(n * sizeof(Point));
Point *hull = malloc(n * sizeof(Point));
if (!points || !hull) {
fclose(in);
fclose(out);
return -1;
}
for (int i = 0; i < n; i++) {
fscanf(in, "%lf %lf", &points[i].x, &points[i].y);
}
int hullSize = construiestePoligon(points, n, hull);
fprintf(out, "%d\n", hullSize);
for (int i = 0; i < hullSize; i++) {
fprintf(out, "%.6f %.6f\n", hull[i].x, hull[i].y);
}
free(points);
free(hull);
fclose(in);
fclose(out);
return 0;
}