Cod sursa(job #2715890)

Utilizator retrogradLucian Bicsi retrograd Data 4 martie 2021 12:55:17
Problema Rubarba Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.44 kb
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using Point = complex<ll>;

ll cross(Point a, Point b) {
  return a.real() * b.imag() - b.real() * a.imag();
}
ll det(Point a, Point b, Point c) { return cross(b - a, c - a); }

namespace std {
  bool operator<(const Point& a, const Point& b) {
    if (a.real() == b.real()) 
      return a.imag() < b.imag();
    return a.real() < b.real();
  }
}

vector<Point> HullHalf(vector<Point>& P, int z) {
  vector<Point> ret; // z = +1 if lower, -1 if upper
  for (auto p : P) {
    while ((int)ret.size() >= 2 &&                
        z * det(ret.end()[-2], ret.end()[-1], p) <= 0)
      ret.pop_back();
    ret.push_back(p);
  }
  return ret;
}
vector<Point> Hull(vector<Point> P) {
  sort(P.begin(), P.end());
  P.erase(unique(P.begin(), P.end()), P.end());
  if (P.size() <= 1) return P;
  auto l = HullHalf(P, +1), u = HullHalf(P, -1); 
  l.insert(l.end(), u.rbegin() + 1, u.rend() - 1);
  return l;
}

int main() {
  ifstream cin("rubarba.in");
  ofstream cout("rubarba.out");

  int n; cin >> n;
  vector<Point> P(n);
  for (int i = 0; i < n; ++i) {
    ll x, y; cin >> x >> y;
    P[i] = {x, y};
  }
  P = Hull(P); n = P.size();
  
  auto rotate = [&](Point p, int rot) {
    rot %= 4;
    if (rot >= 2) p = -p, rot -= 2;
    if (rot == 1) p = {-p.imag(), p.real()};
    return p;
  };
  
  int piv[4] = {0, 0, 0, 0};
  for (int rot = 0; rot < 4; ++rot) 
    for (int i = 0; i < n; ++i) 
      if (rotate(P[i], rot) < rotate(P[piv[rot]], rot))
        piv[rot] = i;

  double best = 2e18;
  for (int it = 0; it < 2 * n; ++it) {
    int adv = 0;
    auto cdir = [&](int rot) {
      int i = piv[rot], j = (i == n - 1 ? 0 : i + 1);
      return rotate(P[j], rot) - rotate(P[i], rot);
    };
    for (int rot = 1; rot < 4; ++rot) {
      auto d1 = cdir(adv), d2 = cdir(rot);
      if (cross(d1, d2) < 0) adv = rot;
    }
    auto dx = rotate(cdir(adv), -adv);
    auto dy = rotate(dx, 1);
    double xmin = 1e10, xmax = -1e10, ymin = 1e10, ymax = -1e10;
    for (int rot = 0; rot < 4; ++rot) {
      auto p = P[piv[rot]];
      double x = cross(dx, p) / sqrt(norm(dx));
      double y = cross(dy, p) / sqrt(norm(dy));
      xmin = min(xmin, x); xmax = max(xmax, x);
      ymin = min(ymin, y); ymax = max(ymax, y);
    }
    double area = (xmax - xmin) * (ymax - ymin);
    best = min(best, area);
    piv[adv] = (piv[adv] == n - 1 ? 0 : piv[adv] + 1);
  }
  cout << fixed << setprecision(2) << best << endl;
  

    
  return 0;
}