Cod sursa(job #3002433)

Utilizator cata00Catalin Francu cata00 Data 14 martie 2023 19:30:37
Problema Rubarba Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.89 kb
// Method: Rotating calipers. Comments at the end.
#include <algorithm>
#include <stdio.h>

#define MAX_N 100'000

typedef struct {
  int x, y;
} point;

point p[MAX_N];
int n;
int st[MAX_N], ss;  // Stack for Graham's scan.

long double min(long double x, long double y) {
  return (x < y) ? x : y;
}

// Cross product p[a]p[b] · p[c]p[d].
long long dot4(int a, int b, int c, int d) {
  return
    (long long)(p[b].x - p[a].x) * (p[d].x - p[c].x) +
    (long long)(p[b].y - p[a].y) * (p[d].y - p[c].y);
}

// Cross product p[a]p[b] · p[a]p[c]
long long dot(int a, int b, int c) {
  return dot4(a, b, a, c);
}

// Signed area. This one uses points, not indices because cmp() calls it.
long long area(point a, point b, point c) {
  return
    (long long)(b.x - a.x) * (c.y - b.y) -
    (long long)(b.y - a.y) * (c.x - b.x);
}

// Square of the Euclidean distance.
long long dist2(point a, point b) {
  return
    (long long)(a.x - b.x) * (a.x - b.x) +
    (long long)(a.y - b.y) * (a.y - b.y);
}

bool cmp(point a, point b) {
  long long d = area(p[0], a, b);
  if (d == 0) {
    // a and b are collinear with p[0]. Put the furthest one first.
    return dist2(a, p[0]) > dist2(b, p[0]);
  } else {
    return d > 0;
  }
}

// Brings the point having the minimum y coordinate in first position.
// Sorts the other points in polar order with respect to the first.
void polar_sort() {
  // Minimum x as tiebreaker.
  int min = 0;
  for (int i = 1; i < n; i++) {
    if ((p[i].y < p[min].y) || (p[i].y == p[min].y && p[i].x < p[min].x)) {
      min = i;
    }
  }
  point tmp = p[0];
  p[0] = p[min];
  p[min] = tmp;

  std::sort(p + 1, p + n, cmp);
}

// Graham's scan convex hull algorithm.
void graham_scan() {
  st[0] = 0;
  st[1] = 1;
  ss = 2;
  for (int i = 2; i < n; i++) {
    // Ignore points on the same ray as the previous point. Since the previous
    // point was further away, the current one won't help.
    if (area(p[0], p[st[ss - 1]], p[i]) != 0) {
      while (area(p[st[ss - 2]], p[st[ss - 1]], p[i]) <= 0) {
        ss--;
      }
      st[ss++] = i;
    }
  }

  // Collect the points on the hull in ccw order.
  for (int i = 0; i < ss; i++) {
    p[i] = p[st[i]];
  }
  n = ss;
}

// Returns the next point in circular fashion.
int next(int k) {
  return (k == n - 1) ? 0 : (k + 1);
}

long double rectangle_area(int b1, int b2, int r, int a, int l) {
  // Note: this is rational. Probably not worth the effort, though.
  return (long double)dot4(b1, b2, l, r)
    / dist2(p[b1], p[b2])
    * area(p[b1], p[b2], p[a]);
}

long double rotating_calipers() {
  // Find the initial right, across and left points for the base P[0]P[1].
  int r = 1, a, l;
  while (dot(0, 1, next(r)) > dot(0, 1, r)) {
    r = next(r);
  }
  a = r;
  while (area(p[0], p[1], p[next(a)]) > area(p[0], p[1], p[a])) {
    a = next(a);
  }
  l = a;
  while (dot(0, 1, next(l)) < dot(0, 1, l)) {
    l = next(l);
  }

  long double min_area = rectangle_area(0, 1, r, a, l);

  // For a visual explanation of why this works, see
  // https://www.youtube.com/watch?v=OaGvH450jRM
  for (int i = 1; i < n; i++) {
    int j = next(i);

    while (dot(i, j, next(r)) > dot(i, j, r)) {
      r = next(r);
    }
    a = r;
    while (area(p[i], p[j], p[next(a)]) > area(p[i], p[j], p[a])) {
      a = next(a);
    }
    l = a;
    while (dot(i, j, next(l)) < dot(i, j, l)) {
      l = next(l);
    }

    min_area = min(min_area, rectangle_area(i, j, r, a, l));
  }

  return min_area;
}

int main() {
  // Read the input data.
  FILE* f = fopen("rubarba.in", "r");
  fscanf(f, "%d", &n);
  for (int i = 0; i < n; i++) {
    fscanf(f, "%d %d", &p[i].x, &p[i].y);
  }
  fclose(f);

  long double result = 0;
  if (n > 2) {
    polar_sort();
    graham_scan();
    if (n > 2) {
      result = rotating_calipers();
    }
  }

  f = fopen("rubarba.out", "w");
  fprintf(f, "%.2Lf\n", result);
  fclose(f);

  return 0;
}

// First, find the convex hull. Next, one of the sides of the hull must
// support the rectangle. Try every side one by one. For every side, determine
// the farthest point to the left, across and right. The smallest rectangle is
// bounded by these extremes.
//
// To find the initial points, say for the side p[0]p[1], notice that the
// rightmost point r maximizes the dot product p[0]p[1] · p[0]p[r]. Similarly
// for the leftmost point l. As for the point across, a, it maximizes the area
// of the triangle p[0]p[1]p[a].
//
// When advancing the support side from p[i]p[i + 1] to p[i + 1]p[i + 2], the
// points r, l and a also advance counterclockwise.
//
// Returns the area of the rectangle supported by b1b2 with extremes r
// (right),  a (across) and l (left).
//
// Having determined i, j = i + 1, r, l and a, what is the area of the
// rectangle? The height of the rectangle is the distance from a to ij. But
// that's also area(triangle aij) / |ij|. The width of the rectangle is the
// vector r - l projected on the ij axis.  But by definition that is (r - l) ·
// ij / |ij| (cross product).