Cod sursa(job #2877302)

Utilizator livliviLivia Magureanu livlivi Data 24 martie 2022 15:20:33
Problema Rubarba Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.19 kb
#include <bits/stdc++.h>
 
using namespace std;
 
typedef pair<double, double> pd;
 
struct Line {
  double a, b, c;
 
  void operator *= (int x) {
    a *= x, b *= x, c *= x;
  }
};
 
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) >= 0;
}
 
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) {
  return {-(p2.second - p1.second), (p2.first - p1.first), p1.first * p2.second - p1.second * p2.first};
}
 
Line perpInPoint(Line l, pd p) {
  // - l.b * p.x + l.a * p.y + l.c = 0
  return {-l.b , l.a, l.b * p.first - l.a * p.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));
}

Line perpLine(Line l) {
  Line ans = {-l.b, l.a, 0};
}
 
int main() {
  ifstream cin("rubarba.in");
  ofstream cout("rubarba.out");
  int n;
  cin >> n;
  vector<pd> points;
  map<pd, bool> mp;
  while (n--) {
    double x, y;
    cin >> x >> y;
    if (!mp[{x, y}]) {
      points.emplace_back(x, y);
      mp[{x, y}] = true;
    }
  }
  cin.close();
  vector<pd> hull = convexHull(points);
 
  // for (int i = 0; i < hull.size(); i++) {
  //   cerr << i << " " << hull[i].first << " " << hull[i].second << endl;
  // }
  //corner cases
  if (hull.size() <= 2) {
    cout << "0\n";
    cout.close();
    return 0;
  }
 
  int ba = 0, ta = 0, la = 0, ra = 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))
      top = i;
  //left & right
  Line perp = perpLine(l);
  int left = 0, right = 0;
  for (int i = 0; i < hull.size(); ++i) {
    if (distToLineSigned(hull[i], perp) < distToLineSigned(hull[left], perp))
      left = i;
    if (distToLineSigned(hull[i], perp) > distToLineSigned(hull[right], perp))
      right = i;
  }
 
  // cerr << "0 " << left << " " << right << "\n";
  ta = top, la = left, ra = right;
  //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);
    Line perp = perpLine(l);
 
    // if (i == 2) {
      // cerr << distToLineSigned(hull[left], perp) << " " << distToLineSigned(hull[(left + 1) % hull.size()], perp) << endl;
      // cerr << distToLineSigned(hull[right], perp) << " " << distToLineSigned(hull[(right + 1) % hull.size()], perp) << endl;
    // }
 
    while (distToLine(hull[(top + 1) % hull.size()], l) > distToLine(hull[top], l))
      top = (top + 1) % hull.size();
    while (distToLineSigned(hull[(left + 1) % hull.size()], perp) < distToLineSigned(hull[left], perp))
      left = (left + 1) % hull.size();
    while (distToLineSigned(hull[(right + 1) % hull.size()], perp) > distToLineSigned(hull[right], perp))
      right = (right + 1) % hull.size();
    // cerr << i << " " << left << " " << right << "\n";
    // cerr << distToLineSigned(hull[right], perp) - distToLineSigned(hull[left], perp) << endl;
    if (ans > distToLine(hull[top], l) * (distToLineSigned(hull[right], perp) - distToLineSigned(hull[left], perp))) {
      ans = distToLine(hull[top], l) * (distToLineSigned(hull[right], perp) - distToLineSigned(hull[left], perp));
      ba = i, ta = top, la = left, ra = right;
    }
  }
  cout << fixed << setprecision(2) << ans << "\n";
  // cerr << ba << " " << ta << " " << la << " " << ra << endl;
  cout.close();
  return 0;
}