Cod sursa(job #2630865)

Utilizator AokijiAlex M Aokiji Data 27 iunie 2020 16:27:54
Problema Rubarba Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.07 kb
#include <bits/stdc++.h>

using namespace std;

const long long MAX_N = 100000;
const double INF = 2000000000;

struct Punct {
  long long x, y;
} v[MAX_N + 5];

struct Dreapta {
  long long a, b, c;
};

Dreapta dreapta(Punct p1, Punct p2) {
  return {
          p2.y - p1.y,
          p1.x - p2.x,
          p1.y * p2.x - p1.x * p2.y
         };
}

Dreapta perp(Punct a, Dreapta d) {
  return {
          -d.b,
          d.a,
          d.b * a.x - d.a * a.y
         };
}

double distd(Punct a, Dreapta d) {
  double aux = sqrt((double)d.a * d.a + d.b * d.b);
  double k = 1 / aux;
  return (a.x * d.a + a.y * d.b + d.c) * k;
}

long long cross_product(Punct P1, Punct P2, Punct P3) {
  return (P2.x - P1.x) * (P3.y - P1.y) -
     (P2.y - P1.y) * (P3.x - P1.x);
}

long long ccw(Punct P1, Punct P2, Punct P3) {
  long long cp = cross_product(P1, P2, P3);
  if (cp < 0)
    return -1;
  if (cp > 0)
    return 1;
  return 0;
}

bool cmp(Punct a, Punct b) {
  return ccw(v[0], a, b) < 0;
}

long long st[MAX_N + 5];

long long nxt(long long i, long long n) {
  if (i + 1 > n)
    return 0;
  return i + 1;
}

int main() {
  freopen("rubarba.in", "r", stdin);
  freopen("rubarba.out", "w", stdout);

  long long n;
  scanf("%lld", &n);

  for (long long i = 0; i < n; ++i) {
    scanf("%lld%lld", &v[i].x, &v[i].y);
    if (v[i].y < v[0].y || (v[i].y == v[0].y && v[i].x < v[0].x))
      swap(v[i], v[0]);
  }

  sort(v + 1, v + n, cmp);

  st[0] = 0;
  st[1] = 1;
  long long top = 1;
  for (long long i = 2; i < n; ++i){
    while (top > 1 && ccw(v[st[top] - 1], v[st[top]], v[i]) >= 0)
      top--;
    st[++top] = i;
  }

  long long ind1, ind2, ind3;
  double di1, di2, di3;
  di1 = di2 = -INF;
  di3 = INF;
  Dreapta d1 = dreapta(v[st[0]], v[st[1]]);
  Dreapta d2 = perp(v[st[0]], d1);
  for (long long i = 0; i <= top; ++i) {
    double dist1 = fabs(distd(v[st[i]], d1));
    double dist2 = distd(v[st[i]], d2);
    if (di1 < dist1) {
      di1 = dist1;
      ind1 = i;
    }
    if (di2 < dist2) {
      di2 = dist2;
      ind2 = i;
    }
    if (di3 > dist2) {
      di3 = dist2;
      ind3 = i;
    }
  }

  double dst = di2 - di3;
  double ans = dst * di1;

  for (long long i = 1; i < top; ++i) {
    d1 = dreapta(v[st[i]], v[st[i + 1]]);
    d2 = perp(v[st[i]], d1);
    di1 = distd(v[st[ind1]], d1);
    di2 = distd(v[st[ind2]], d2);
    di3 = distd(v[st[ind3]], d2);
    double aux = fabs(distd(v[st[nxt(ind1, top)]], d1));
    while (aux >= di1) {
      di1 = aux;
      ind1 = nxt(ind1, top);
      aux = fabs(distd(v[st[nxt(ind1, top)]], d1));
    }
    aux = distd(v[st[nxt(ind2, top)]], d2);
    while (aux >= di2) {
      di2 = aux;
      ind2 = nxt(ind2, top);
      aux = distd(v[st[nxt(ind2, top)]], d2);
    }
    aux = distd(v[st[nxt(ind3, top)]], d2);
    while (aux <= di3) {
      di3 = aux;
      ind3 = nxt(ind3, top);
      aux = distd(v[st[nxt(ind3, top)]], d2);
    }
    aux = di2 - di3;
    ans = min(ans, aux * di1);
  }

  printf("%.2f", ans);

  return 0;
}