Cod sursa(job #3357331)

Utilizator Dumitru_SerbinaDumitru Serbina Dumitru_Serbina Data 8 iunie 2026 22:01:31
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 2.45 kb
#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;
}