Cod sursa(job #3359277)

Utilizator SimionescuGabrielSimionescu Gabriel SimionescuGabriel Data 26 iunie 2026 14:35:53
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <stdio.h>
#include <stdlib.h>

#define MAXN 120005

typedef struct {
  double x, y;
} Point;

Point p[MAXN];
Point hull[2 * MAXN];

int cmp(const void *a, const void *b) {
  Point *A = (Point *)a;
  Point *B = (Point *)b;

  if (A->x < B->x)
    return -1;
  if (A->x > B->x)
    return 1;

  if (A->y < B->y)
    return -1;
  if (A->y > B->y)
    return 1;

  return 0;
}

double cross(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() {
  freopen("infasuratoare.in", "r", stdin);
  freopen("infasuratoare.out", "w", stdout);

  int n;
  scanf("%d", &n);

  for (int i = 0; i < n; i++) {
    scanf("%lf %lf", &p[i].x, &p[i].y);
  }

  qsort(p, n, sizeof(Point), cmp);

  int m = 0;

  for (int i = 0; i < n; i++) {
    while (m >= 2 && cross(hull[m - 2], hull[m - 1], p[i]) <= 0)
      m--;

    hull[m++] = p[i];
  }

  int t = m + 1;

  for (int i = n - 2; i >= 0; i--) {
    while (m >= t && cross(hull[m - 2], hull[m - 1], p[i]) <= 0)
      m--;

    hull[m++] = p[i];
  }

  m--;

  printf("%d\n", m);

  for (int i = 0; i < m; i++) {
    printf("%.6lf %.6lf\n", hull[i].x, hull[i].y);
  }

  return 0;
}