Pagini recente » Cod sursa (job #2963349) | Cod sursa (job #3257180) | Cod sursa (job #79888) | Cod sursa (job #3275585) | Cod sursa (job #3300067)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
//https://infoarena.ro/problema/infasuratoare
#define MAXIM 120000
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;
}
int compare(const void *a, const void *b) {
Point *p1 = (Point *)a;
Point *p2 = (Point *)b;
double cross = produsVectorial(pivot, *p1, *p2);
if (fabs(cross) <0.0000001) {
double d1 = distanta(pivot, *p1);
double d2 = distanta(pivot, *p2);
if (d1 < d2) return -1;
if (d1 > d2) return 1;
return 0;
}
if (cross > 0) return -1;
return 1;
}
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];
qsort(points + 1, n - 1, sizeof(Point), compare);
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;
}