Pagini recente » Statistici dragos (Asandu178) | Statistici yoyoo29 (yoyoo29) | Cod sursa (job #3358231) | Statistici Sinziana Tibu (sinziana30) | Cod sursa (job #3359392)
#include <stdio.h>
#include <stdlib.h>
typedef struct {
double x, y;
} Point;
int comparePoints(const void* a, const void* b) {
Point* p1 = (Point*)a;
Point* p2 = (Point*)b;
if (p1->x != p2->x) {
return (p1->x < p2->x) ? -1 : 1;
}
if (p1->y != p2->y) {
return (p1->y < p2->y) ? -1 : 1;
}
return 0;
}
double crossProduct(Point a, Point b, Point c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
int main() {
FILE *fin = fopen("infasuratoare.in", "r");
FILE *fout = fopen("infasuratoare.out", "w");
if (!fin || !fout) return 0;
int n;
if (fscanf(fin, "%d", &n) != 1) return 0;
Point* points = (Point*)malloc(n * sizeof(Point));
for (int i = 0; i < n; ++i) {
fscanf(fin, "%lf %lf", &points[i].x, &points[i].y);
}
qsort(points, n, sizeof(Point), comparePoints);
Point* hull = (Point*)malloc(2 * n * sizeof(Point));
int h_size = 0;
for (int i = 0; i < n; ++i) {
while (h_size >= 2 && crossProduct(hull[h_size - 2], hull[h_size - 1], points[i]) <= 1e-11) {
h_size--;
}
hull[h_size++] = points[i];
}
int lower_size = h_size;
for (int i = n - 2; i >= 0; --i) {
while (h_size > lower_size && crossProduct(hull[h_size - 2], hull[h_size - 1], points[i]) <= 1e-11) {
h_size--;
}
hull[h_size++] = points[i];
}
if (h_size > 1) {
h_size--;
}
int start_idx = 0;
for (int i = 1; i < h_size; ++i) {
if (hull[i].y < hull[start_idx].y || (hull[i].y == hull[start_idx].y && hull[i].x < hull[start_idx].x)) {
start_idx = i;
}
}
fprintf(fout, "%d\n", h_size);
for (int i = 0; i < h_size; ++i) {
int idx = (start_idx + i) % h_size;
fprintf(fout, "%.6f %.6f\n", hull[idx].x, hull[idx].y);
}
free(points);
free(hull);
fclose(fin);
fclose(fout);
return 0;
}