Cod sursa(job #2700105)

Utilizator retrogradLucian Bicsi retrograd Data 26 ianuarie 2021 16:06:28
Problema Camera Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.76 kb
#include <bits/stdc++.h>

using namespace std;

using T = int; 
using T2 = long long;
using T4 = __int128_t;
const T2 INF = 1e18;

struct Line { T a, b; T2 c; };

bool operator<(Line m, Line n) {
  auto half = [&](Line m) { 
    return m.b < 0 || m.b == 0 && m.a < 0; };
  return make_tuple(half(m), (T2)m.b * n.a, m.c) < 
    make_tuple(half(n), (T2)m.a * n.b, n.c);
}
tuple<T4, T4, T2> inter(Line m, Line n) {
  T2 d = (T2)m.a * n.b - (T2)m.b * n.a; 
  // assert(d);
  T4 x = (T4)m.c * n.b - (T4)m.b * n.c; 
  T4 y = (T4)m.a * n.c - (T4)m.c * n.a;
  if (d < 0) x = -x, y = -y, d = -d;
  return {x, y, d};
}

ostream& operator<<(ostream& out, Line l) {
  out << "(" << l.a << " * x + " << l.b << " * y <= " << l.c << ")";
  return out;
}
struct HalfplaneSet : set<Line> {
  HalfplaneSet() {
    insert({+1, 0, INF}); insert({0, +1, INF});
    insert({-1, 0, INF}); insert({0, -1, INF});
  };

  auto prv(auto it) { return --(it == begin() ? end() : it); }
  auto nxt(auto it) { return (++it == end() ? begin() : it); }
  bool bad(auto it) {
    auto l = *it, pl = *prv(it), nl = *nxt(it);
    T2 det = (T2)pl.a * nl.b - (T2)pl.b * nl.a;
    T4 x, y; T2 d; tie(x, y, d) = inter(pl, nl);
    //auto [x, y, d] = inter(pl, nl);
    bool sat = l.a * x + l.b * y <= (T4)l.c * d;
    if (det < 0 && !sat) {
      /*
      cerr << "UNSAT: " << *it << endl;
      cerr << "  prv: " << *prv(it) << endl;
      cerr << "  nxt: " << *nxt(it) << endl;
      cerr << "  intersection: " << 1.0 * x / d << " " << 1.0 * y / d << endl;
      cerr << "  det: " << det << " satisfies: " << sat << endl;*/
      clear();
    }
    /*
    if (det >= 0 && sat) {
      cerr << "bad: " << *it << endl;
      cerr << "  prv: " << *prv(it) << endl;
      cerr << "  nxt: " << *nxt(it) << endl;
      cerr << "  intersection: " << 1.0 * x / d << " " << 1.0 * y / d << endl;
      cerr << "  det: " << det << " satisfies: " << sat << endl;
    }*/
    return det >= 0 && sat;
  };

  void Cut(T a, T b, T2 c) { // add ax + by <= c
    if (empty()) return;
    auto it = insert({a, b, c}).first;
    //cerr << "cut: " << *it << endl;
    if (bad(it)) erase(it);
    while (size() > 2) {
      auto nit = nxt(it);
      if (bad(nit)) erase(nit);
      else break;
    }
    while (size() > 2) {
      auto pit = prv(it);
      if (bad(pit)) erase(pit);
      else break;
    }
    if (size() <= 2) clear();
    //cerr << " => " << size() << endl;
  }

  double Maximize(T a, T b) { // max ax + by
    if (empty()) return -1/0.;
    auto it = lower_bound({-b, a});
    if (it == end()) it = begin();
    T4 x, y; T2 d; tie(x, y, d) = inter(*prv(it), *it);
    //auto [x, y, d] = inter(*prv(it), *it);
    return (1.0 * a * x + 1.0 * b * y) / d;
  }

  double Area() {
    if (empty()) return 0.;
    double total = 0.;
    for (auto it = begin(); it != end(); ++it) {
      T4 x1, x2, y1, y2; T2 d1, d2;
      tie(x1, y1, d1) = inter(*prv(it), *it);
      tie(x2, y2, d2) = inter(*it, *nxt(it));
      //auto [x1, y1, d1] = inter(*prv(it), *it);
      //auto [x2, y2, d2] = inter(*it, *nxt(it));
      total += (1.0 * x1 * y2 - 1.0 * x2 * y1) / d1 / d2;
    }
    return total * 0.5;
  }
};

int main() {
  ifstream cin("camera.in");
  ofstream cout("camera.out");

  int n; cin >> n;

  vector<T> x(n), y(n);
  for (int i = 0; i < n; ++i) 
    cin >> x[i] >> y[i];
  
  double ans = 0;
  for (int rev = 0; rev < 2; ++rev) {
    HalfplaneSet HS;
    for (int j = n - 1, i = 0; i < n; j = i++) {
      T a = y[i] - y[j], b = x[j] - x[i];
      T2 c = (T2)a * x[i] + (T2)b * y[i];
      HS.Cut(a, b, c);
    }
    /*
    if (HS.size()) {
      cerr << "FINAL\n";
      for (auto x : HS) cerr << x << "\n";
    }*/
    ans = max(ans, HS.Area());
    reverse(x.begin(), x.end()); 
    reverse(y.begin(), y.end());
  }
  cout << fixed << setprecision(2) << ans << endl;

  return 0;
}