Cod sursa(job #2715946)

Utilizator retrogradLucian Bicsi retrograd Data 4 martie 2021 13:32:32
Problema Rubarba Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.85 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;
}

struct InParser {
  FILE *fin;
  char *buff;
  int sp;

  char read_ch() {
    ++sp;
    if (sp == (1 << 16)) {
      sp = 0;
      fread(buff, 1, (1 << 16), fin);
    }
    return buff[sp];
  }

  InParser(const char* nume) {
    fin = fopen(nume, "r");
    buff = new char[1 << 16]();
    sp = (1 << 16) - 1;
  }

  InParser& operator >> (int &n) {
    char c;
    while (!isdigit(c = read_ch()) && c != '-');
    int sgn = 1;
    if (c == '-') {
      n = 0;
      sgn = -1;
    } else {
      n = c - '0';
    }
    while (isdigit(c = read_ch())) {
      n = 10 * n + c - '0';
    }
    n *= sgn;
    return *this;
  }
};

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

  int n; cin >> n;
  vector<Point> P(n);
  for (int i = 0; i < n; ++i) {
    int 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 < n; ++it) {
    int adv = 0;
    auto cdir = [&](int rot) {
      int i = piv[rot], j = (i == n - 1 ? 0 : i + 1);
      return rotate(P[j] - P[i], rot);
    };
    for (int rot = 1; rot < 4; ++rot) 
      if (cross(cdir(adv), cdir(rot)) < 0) 
        adv = rot;
    auto dx = rotate(cdir(adv), 4 - adv); 
    auto dy = rotate(dx, 1);
    ll w = cross(P[piv[(adv + 0) % 4]] - P[piv[(adv + 2) % 4]], dx);
    ll h = cross(P[piv[(adv + 1) % 4]] - P[piv[(adv + 3) % 4]], dy);
    double area = 1.0 * abs(w) / sqrt(norm(dx)) * abs(h) / sqrt(norm(dy));
    best = min(best, area);
    piv[adv] = (piv[adv] == n - 1 ? 0 : piv[adv] + 1);
  }
  cout << fixed << setprecision(2) << best << endl;
  

    
  return 0;
}