Cod sursa(job #3359133)

Utilizator tomescuioanacasianaTomescu Ioana-Casiana tomescuioanacasiana Data 24 iunie 2026 22:58:56
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <stdio.h>
#include <stdlib.h>

#define EPS 1e-12

typedef struct
{
  double x, y;
} Point;

Point P[120005];
Point H[240005];

int cmp(const void *a, const void *b)
{
  Point *p1 = (Point *)a;
  Point *p2 = (Point *)b;
  if(p1->x < p2->x){
    return -1;
  }
  if(p1->x > p2->x){
    return 1;
  }
  if(p1->y < p2->y){
    return -1;
  }
  if(p1->y > p2->y){
    return 1;
  }
  return 0;
}

double cross_product(Point o, Point a, Point b)
{
  return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}

int main(void)
{
  FILE *fin = fopen("infasuratoare.in", "r");
  FILE *fout = fopen("infasuratoare.out", "w");
  int n, i, k = 0, t;
  fscanf(fin, "%d", &n);
  for(i = 0; i < n; i++){
    fscanf(fin, "%lf %lf", &P[i].x, &P[i].y);
  }
  qsort(P, n, sizeof(Point), cmp);
  for(i = 0; i < n; i++){
    while(k >= 2 && cross_product(H[k - 2], H[k - 1], P[i]) <= EPS){
      k--;
    }
    H[k++] = P[i];
  }
  t = k + 1;
  for(i = n - 2; i >= 0; i--){
    while(k >= t && cross_product(H[k - 2], H[k - 1], P[i]) <= EPS){
      k--;
    }
    H[k++] = P[i];
  }
  k--;
  int min_idx = 0;
  for(i = 1; i < k; i++){
    if(H[i].y < H[min_idx].y || (H[i].y == H[min_idx].y && H[i].x < H[min_idx].x)){
      min_idx = i;
    }
  }
  fprintf(fout, "%d\n", k);
  for(i = 0; i < k; i++){
    int idx = (min_idx + i) % k;
    fprintf(fout, "%.6lf %.6lf\n", H[idx].x, H[idx].y);
  }
  fclose(fin);
  fclose(fout);
  return 0;
}