Cod sursa(job #2402298)

Utilizator lucametehauDart Monkey lucametehau Data 10 aprilie 2019 16:23:11
Problema Rubarba Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#define pii pair <int, int>
#define x first
#define y second

using namespace std;

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

int n, vf;
long double area;

pii v[100005], w[100005];
int st[100005];
bool in[100005];

bool orientation(pii a, pii b, pii c) {
  return 1LL * (c.y - a.y) * (b.x - a.x) - 1LL * (a.y - b.y) * (a.x - c.x) <= 0;
}

void convex_hull() {
  sort(v + 1, v + n + 1);
  st[++vf] = 1; st[++vf] = 2;
  in[2] = 1;
  for(int i = 1, j = 1; i; i += (j = (i == n ? -j : j))) {
    if(in[i])
      continue;
    while(vf > 1 && orientation(v[st[vf - 1]], v[st[vf]], v[i]))
      in[st[vf--]] = 0;
    st[++vf] = i;
    in[st[vf]] = 1;
  }
}

long double sqr(long double x) {
  return x * x;
}

long double det(pii a, pii b, pii c) {
  return 1LL * a.x * b.y + 1LL * a.y * c.x + 1LL * b.x * c.y - 1LL * a.x * c.y - 1LL * a.y * b.x - 1LL * b.y * c.x;
}

int main() {
  cin >> n;
  for(int i = 1; i <= n; i++)
    cin >> v[i].x >> v[i].y;
  convex_hull();
  vf--;
  n = vf;
  for(int i = 1; i <= n; i++)
    w[i] = v[st[i]];
  for(int i = 1; i <= n; i++)
    v[i] = w[i];
  v[n + 1] = v[1];
  area = 1e18;
  for(int i = 1; i <= n; i++) {
    long double d = sqr(v[i].x - v[i + 1].x) + sqr(v[i].y - v[i + 1].y), hmax = 0, v1 = 0, v2 = 0;
    d = sqrt(d);
    for(int j = 1; j <= n; j++) {
      if(j == i || j == i + 1)
        continue;
      long double h = abs((long double)det(v[i], v[i + 1], v[j]) / d), ab = sqr(v[i].x - v[j].x) + sqr(v[i].y - v[j].y), ac = sqr(v[i + 1].x - v[j].x) + sqr(v[i + 1].y - v[j].y);
      hmax = max(hmax, h);
      ab -= sqr(h);
      ac -= sqr(h);
      if(abs(sqr(d) - ab - ac) <= 1e-12)
        continue;
      if(ab < ac)
        v1 = max(v1, ab);
      else
        v2 = max(v2, ac);
    }
    v1 = sqrt(v1); v2 = sqrt(v2);
    area = min(area, hmax * (v1 + v2 + d));
  }
  cout << fixed << setprecision(2) << area;
  return 0;
}