Pagini recente » Borderou de evaluare (job #3330473) | Borderou de evaluare (job #3332823) | Monitorul de evaluare | Borderou de evaluare (job #3321129) | Cod sursa (job #3357331)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct {
double x;
double y;
} point_t;
static point_t pivot = {0};
double cross_product(point_t o, point_t a, point_t b){
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
double distance_sq(point_t a, point_t b){
double dx = a.x - b.x;
double dy = a.y - b.y;
return dx * dx + dy * dy;
}
int cmp_polar(const void *a, const void *b){
point_t *pa = (point_t*)a;
point_t *pb = (point_t*)b;
double cross = cross_product(pivot, *pa, *pb);
if(cross > 1e-12) return -1;
if(cross < -1e-12) return 1;
double da = distance_sq(pivot, *pa);
double db = distance_sq(pivot, *pb);
if(da < db) return -1;
if(da > db) return 1;
return 0;
}
int main(void){
FILE *fin = fopen("infasuratoare.in", "r");
if(fin == NULL){
perror("infasuratoare.in");
return 1;
}
int n = 0;
fscanf(fin, "%d", &n);
point_t *points = (point_t*)malloc(sizeof(point_t) * n);
if(points == NULL){
perror("malloc");
fclose(fin);
return 1;
}
for(int i = 0; i < n; i++){
fscanf(fin, "%lf %lf", &points[i].x, &points[i].y);
}
fclose(fin);
// find bottom-most point (leftmost if tie) to use as pivot
int pivot_idx = 0;
for(int i = 1; i < n; i++){
if(points[i].y < points[pivot_idx].y ||
(points[i].y == points[pivot_idx].y && points[i].x < points[pivot_idx].x)){
pivot_idx = i;
}
}
// swap pivot to index 0
point_t temp = points[0];
points[0] = points[pivot_idx];
points[pivot_idx] = temp;
pivot = points[0];
// sort remaining points by polar angle relative to pivot
qsort(points + 1, n - 1, sizeof(point_t), cmp_polar);
// graham scan using an explicit stack (array-based)
point_t *stack = (point_t*)malloc(sizeof(point_t) * n);
int stack_size = 0;
if(stack == NULL){
perror("malloc");
free(points);
return 1;
}
for(int i = 0; i < n; i++){
while(stack_size >= 2 &&
cross_product(stack[stack_size - 2], stack[stack_size - 1], points[i]) <= 1e-12){
stack_size--;
}
stack[stack_size] = points[i];
stack_size++;
}
FILE *fout = fopen("infasuratoare.out", "w");
if(fout == NULL){
perror("infasuratoare.out");
free(points);
free(stack);
return 1;
}
fprintf(fout, "%d\n", stack_size);
for(int i = 0; i < stack_size; i++){
fprintf(fout, "%lf %lf\n", stack[i].x, stack[i].y);
}
fclose(fout);
free(points);
free(stack);
return 0;
}