Cod sursa(job #2873223)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 18 martie 2022 21:58:20
Problema Rubarba Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.22 kb
#include <bits/stdc++.h>

using namespace std;

typedef pair<double, double> pd;

const double EPS = 1e-8;

struct Line {
  double a, b, c;
};

bool shouldPop(pd a, pd b, pd c) {
  //cross product >= 0
  b = {b.first - a.first, b.second - a.second};
  c = {c.first - a.first, c.second - a.second};
  return (b.first * c.second - b.second * c.first) >= EPS;
}

vector<pd> convexHull(vector<pd>& points) {
  vector<pd> hull;
  sort(points.begin(), points.end());
  for (int cnt = 0; cnt < 2; ++cnt) {
    vector<pd> st;
    for (auto i: points) {
      if (cnt == 1)
        i.second = -i.second;
      while (st.size() > 1 && shouldPop(st.end()[-2], st.end()[-1], i))
        st.pop_back();
      st.push_back(i);
    }
    if (cnt == 1) {
      st.pop_back();
      reverse(st.begin(), st.end());
      st.pop_back();
      for (auto& i: st)
        i.second = -i.second;
    }
    hull.insert(hull.end(), st.begin(), st.end());
  }
  return hull;
}

Line lineEquation(pd p1, pd p2) {
  double slope = (p2.second - p1.second) / (p2.first - p1.first);
  return {-slope, 1, p1.first * slope - p1.second};
}

double distToLineSigned(pd p, Line l) {
  return (l.a * p.first + l.b * p.second + l.c) / sqrt(l.a * l.a + l.b * l.b);
}

double distToLine(pd p, Line l) {
  return abs(distToLineSigned(p, l));
}

int main() {
  ifstream cin("rubarba.in");
  ofstream cout("rubarba.out");
  int n;
  cin >> n;
  vector<pd> points;
  while (n--) {
    double x, y;
    cin >> x >> y;
    points.emplace_back(x, y);
  }
  cin.close();
  vector<pd> hull = convexHull(points);
  //corner cases
  if (hull.size() <= 2) {
    cout << "0\n";
    cin.close();
    cout.close();
    return 0;
  }
  //init
  pd a = hull[0], b = hull[1];
  Line l = lineEquation(a, b);
  //topmost
  int top = 0;
  for (int i = 2; i < hull.size(); ++i)
    if (distToLine(hull[i], l) - distToLine(hull[top], l) >= EPS)
      top = i;
  //left & right
  pd mid = {(a.first + b.first) / 2, (a.second + b.second) / 2};
  Line perp = {-l.b / l.a, 1, l.b / l.a * mid.first - mid.second};
  int left = 0, right = 0;
  for (int i = 0; i < hull.size(); ++i) {
    if (distToLineSigned(hull[left], perp) - distToLineSigned(hull[i], perp) >= EPS)
      left = i;
    if (distToLineSigned(hull[i], perp) - distToLineSigned(hull[right], perp) >= EPS)
      right = i;
  }
  //rotation
  double ans = distToLine(hull[top], l) * (distToLine(hull[left], perp) + distToLine(hull[right], perp));
  for (int i = 1; i < hull.size(); ++i) {
    a = hull[i], b = hull[(i + 1) % hull.size()];
    l = lineEquation(a, b);
    mid = {(a.first + b.first) / 2, (a.second + b.second) / 2};
    perp = {-l.b / l.a, 1, l.b / l.a * mid.first - mid.second};
    while (distToLine(hull[(top + 1) % hull.size()], l) - distToLine(hull[top], l) >= EPS)
      top = (top + 1) % hull.size();
    while (distToLine(hull[(left + 1) % hull.size()], perp) - distToLine(hull[left], perp) >= EPS)
      left = (left + 1) % hull.size();
    while (distToLine(hull[(right + 1) % hull.size()], perp) - distToLine(hull[right], perp) >= EPS)
      right = (right + 1) % hull.size();
    ans = min(ans, distToLine(hull[top], l) * (distToLine(hull[left], perp) + distToLine(hull[right], perp)));
  }
  cout << fixed << setprecision(2) << ans << "\n";
  cout.close();
  return 0;
}