Cod sursa(job #2402605)

Utilizator lucametehauDart Monkey lucametehau Data 10 aprilie 2019 20:44:03
Problema Rubarba Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#define pii pair <long double, long double>
#define x first
#define y second

using namespace std;

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

const long double EPS = 1e-12;

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 (c.y - a.y) * (b.x - a.x) - (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 abs(a.x * b.y + a.y * c.x + b.x * c.y - a.x * c.y - a.y * b.x - b.y * c.x);
}

long double dist(pii a, pii b) {
  return sqr(a.x - b.x) + sqr(a.y - b.y);
}

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 = 1e12;
  for(int i = 1; i <= n; i++) {
    long double hmax = 0, v1 = 0, v2 = 0, ab, ac, d2 = dist(v[i], v[i + 1]);
    for(int j = 1; j <= n; j++) {
      if(j == i || j == i + 1)
        continue;
      long double h = (long double)det(v[i], v[i + 1], v[j]) / d2 * det(v[i], v[i + 1], v[j]);
      if(h > hmax)
        hmax = h;
      ab = dist(v[i], v[j]) - h; ac = dist(v[i + 1], v[j]) - h;
      if(ab - d2 <= EPS && ac - d2 <= EPS)
        continue;
      if(ab <= ac) {
        if(ab > v1)
          v1 = ab;
      } else {
        if(ac > v2)
          v2 = ac;
      }
    }
    v1 = sqrtl(v1); v2 = sqrtl(v2); hmax = sqrtl(hmax); d2 = sqrtl(d2);
    area = min(area, hmax * (v1 + v2 + d2));
  }
  cout << fixed << setprecision(2) << area;
  return 0;
}