AsiaYokohama2019J.cpp

#include <bits/stdc++.h>

using ld = long double;
using P = std::complex<ld>;

const ld eps = 1e-9;

ld dot (P a, P b) { return real(conj(a) * b); }
ld cross (P a, P b) { return imag(conj(a) * b); }

P is_ll(P sa, P sb, P ta, P tb) {
  P sv = sb - sa, tv = tb - ta;
  return sa + sv * cross(tv, ta - sa) / cross(tv, sv);
}

std::vector<P> ConvexCut(const std::vector<P> &g, P la, P lb) {
  std::vector<P> res;
  const int n = g.size();
  for (int i = 0; i < n; ++i) {
    P v1 = lb - la, v2 = g[i] - la, v3 = g[(i+1)%n] - la;
    if (cross(v1, v2) > -eps) res.push_back(g[i]);
    if (cross(v1, v2) * cross(v1, v3) < -eps)
      res.push_back(is_ll(la, lb, g[i], g[(i+1)%n]));
  }
  return res;
}

int main() {
  int n;
  scanf("%d", &n);
  std::vector<P> p;
  for (int i = 0; i < n; ++i) {
    ld x, y;
    scanf("%Lf%Lf", &x, &y);
    p.emplace_back(x, y);
  }
  std::vector<ld> next(n);
  for (int i = 0; i < n; ++i) {
    ld dist = 1e50;
    for (int j = 0; j < n; ++j) {
      P p1 = p[(i+1)%n] - p[i], p2 = p[j] - p[i], p3 = p[(j+1)%n] - p[i];
      if (cross(p1, p3 - p2) < eps || cross(p2, p1) * cross(p3, p1) > eps) continue;
      P h = is_ll(P(0, 0), p1, p2, p3);
      ld d = abs(h - p1);
      if (d < dist && d < abs(h)) {
        dist = d;
        next[i] = j + abs(h - p2) / abs(p3 - p2);
      }
    }
  }
  std::vector<P> g{P(0, 0), P(10000, 0), P(10000, 10000), P(0, 10000)};
  for (int i = 0; i < n; ++i) {
    bool is_overlapped = false;
    for (int j = 0; j < n; ++j) {
      ld i_begin = fmod(i - j + n, n);
      ld i_end = fmod(next[i] - j - 1 + n, n);
      ld j_end = fmod(next[j] - j - 1 + n, n);
      if (i != j && i_begin < i_end + eps && i_end < j_end + eps) is_overlapped = true;
      if (i_begin < j_end && i_end < i_begin) g = std::vector<P>();
    }
    if (!is_overlapped) g = ConvexCut(g, p[i], p[(i+1)%n]);
  }
  ld res = 0;
  const int m = g.size();
  for (int i = 0; i < m; ++i) res += cross(g[i], g[(i+1)%m]) / 2;
  printf("%.10Lf\n", res);
  return 0;
}