puzzle2.cpp

#include <bits/stdc++.h>
using namespace std;

const double EPS = 1e-7;

inline bool zero(const double x) { return fabs(x) < EPS; }
inline bool equal(const double a, const double b) { return zero(a - b); }

struct Point {
  double x, y;
  Point operator+(const Point& p) const { return {x + p.x, y + p.y}; }
  Point operator-(const Point& p) const { return {x - p.x, y - p.y}; }
  double cross(const Point& p) const { return x * p.y - y * p.x; }
  double dist(const Point& p) const { return hypot(x - p.x, y - p.y); }

  void operator-=(const Point& p) {
    x -= p.x;
    y -= p.y;
  }
  bool operator==(const Point& p) const { return equal(x, p.x) && equal(y, p.y); }
  double operator*(const Point& p) const { return x * p.x + y * p.y; }

  Point rot_ccw(const double t) const {
    return {x * cos(t) - y * sin(t), x * sin(t) + y * cos(t)};
  }

  Point rot_ccw() const { return {-y, x}; }
};

short orientation(const Point& o, const Point& a, const Point& b) {
  const double cross = (a - o).cross(b - o);
  if (zero(cross)) return 0;
  return cross > 0 ? 1 : -1;
}

struct Segment {
  Point p, q;
  double length() const { return p.dist(q); }
  inline bool face_right() const { return !is_horizontal() && p.y < q.y; }
  inline bool face_left() const { return !is_horizontal() && p.y > q.y; }
  double common_length(Segment s) const {
    if (contains(s.p) && contains(s.q)) return s.length();
    if (s.contains(p) && s.contains(q)) return length();
    return common_length_aux(s);
  }

  bool is_horizontal() const { return equal(p.y, q.y); }

  bool intersect(const Segment& s) const {
    const short o1 = orientation(p, q, s.p);
    const short o2 = orientation(p, q, s.q);
    const short o3 = orientation(s.p, s.q, p);
    const short o4 = orientation(s.p, s.q, q);
    return o1 * o2 < 0 && o3 * o4 < 0;
  }

  double horizontal_distance(const Point& v) const {
    if (equal(p.x, q.x)) return v.x - p.x;
    const double slope = (q.y - p.y) / (q.x - p.x);
    const double B = p.y - p.x * slope;
    return v.x - (v.y - B) / slope;
  }

  bool contains_except_endpoints(const Point& r) const {
    if (orientation(p, q, r) != 0) return false;
    return (q - p) * (r - p) > EPS && (p - q) * (r - q) > EPS;
  }

 private:
  bool contains(const Point& r) const {
    return p == r || q == r || contains_except_endpoints(r);
  }

  double common_length_aux(const Segment& s) const {
    if (contains(s.p) && s.contains(p)) return p.dist(s.p);
    if (contains(s.p) && s.contains(q)) return q.dist(s.p);
    if (contains(s.q) && s.contains(p)) return p.dist(s.q);
    if (contains(s.q) && s.contains(q)) return q.dist(s.q);
    return 0;
  }
};

inline Point vertex_at(const vector<Point>& polygon, int i) {
  int n = (int)polygon.size();
  i = (i + (n << 10)) % n;
  return polygon[i];
}

double angle(const Point& a, const Point& b) {
  const double x = atan2(a.cross(b), a * b);
  return x < 0 ? x + 2 * M_PI : x;
}

int prev_i = 0, prev_j = 0;

bool intersection_aux(const vector<Point>& p1, const vector<Point>& p2, int i, int j) {
  const Point &a0 = vertex_at(p1, i - 1), &a1 = vertex_at(p1, i),
              &a2 = vertex_at(p1, i + 1);
  const Point &b0 = vertex_at(p2, j - 1), &b1 = vertex_at(p2, j),
              &b2 = vertex_at(p2, j + 1);

  if (Segment{a1, a2}.intersect({b1, b2})) goto return_true;

  if (Segment{b1, b2}.contains_except_endpoints(a1)) {
    if (orientation(b1, b2, a2) == 1) goto return_true;
    if (orientation(b1, b2, a0) == 1) goto return_true;
  }
  if (Segment{a1, a2}.contains_except_endpoints(b1)) {
    if (orientation(a1, a2, b2) == 1) goto return_true;
    if (orientation(a1, a2, b0) == 1) goto return_true;
  }

  if (a1 == b1) {
    const double th = angle(b2 - b1, b0 - b1);
    double th2 = angle(b2 - b1, a0 - b1);
    if (th2 > EPS && th2 < th - EPS) goto return_true;
    th2 = angle(b2 - b1, a2 - b1);
    if (th2 > EPS && th2 < th - EPS) goto return_true;
  }

  return false;

return_true:
  prev_i = i;
  prev_j = j;
  return true;
}

bool intersection(const vector<Point>& p1, const vector<Point>& p2) {
  const int iters_i = (p1.size() / 2) + 1;
  const int iters_j = (p2.size() / 2) + 1;

  for (int i = 0; i < iters_i; i++) {
    for (int j = 0; j < iters_j; j++) {
      if (intersection_aux(p1, p2, prev_i + i, prev_j + j)) return true;
      if (j > 0 && intersection_aux(p1, p2, prev_i + i, prev_j - j)) return true;
    }

    for (int j = 0; i != 0 && j < iters_j; j++) {
      if (intersection_aux(p1, p2, prev_i - i, prev_j + j)) return true;
      if (j > 0 && intersection_aux(p1, p2, prev_i - i, prev_j - j)) return true;
    }
  }
  return false;
}

vector<vector<Point>> create_rotations(vector<Point> polygon, const bool invert) {
  vector<vector<Point>> polygons;
  for (int i = 0; i < (int)polygon.size(); i++) {
    const Point p = polygon[i];
    for (Point& point : polygon) point -= p;
    const Point q = vertex_at(polygon, i + 1);
    const double ang = atan2(q.y, -q.x);
    for (Point& point : polygon) point = point.rot_ccw(ang);
    const Point new_q = vertex_at(polygon, i + 1);
    for (Point& point : polygon) point -= new_q;
    if (invert)
      for (Point& p : polygon) p = p.rot_ccw().rot_ccw();
    polygons.push_back(polygon);
  }

  return polygons;
}

double common_boundary_length(const vector<Point>& polygon1,
                              const vector<Point>& polygon2) {
  double total = 0;

  for (int i = 0; i < (int)polygon1.size(); i++) {
    const Segment edge1{polygon1[i], vertex_at(polygon1, i + 1)};
    for (int j = 0; j < (int)polygon2.size(); j++) {
      const Segment edge2{polygon2[j], vertex_at(polygon2, j + 1)};
      total += edge1.common_length(edge2);
    }
  }

  return total;
}

inline bool range_contains(double a, double b, const double x) {
  if (a > b) swap(a, b);
  return a <= x + EPS && x - EPS <= b;
}

double optimal_shift(vector<Point> polygon1, const vector<Point>& polygon2,
                     const double base1, const double base2) {
  const double max_shift = base1 + base2;
  vector<double> shifts{base1, base2};

  auto collect_shifts = [&](const vector<Point>& polygon_edges,
                            const vector<Point>& polygon_vertices, const bool right) {
    for (int i = 0; i < (int)polygon_edges.size(); i++) {
      const Segment wall{polygon_edges[i], vertex_at(polygon_edges, i + 1)};
      if (wall.is_horizontal()) continue;

      for (int j = 0; j < (int)polygon_vertices.size(); j++) {
        const auto v = polygon_vertices[j];

        if (!range_contains(wall.p.y, wall.q.y, v.y)) continue;

        const auto v0 = vertex_at(polygon_vertices, j - 1);
        const auto v2 = vertex_at(polygon_vertices, j + 1);
        if (orientation(v0, v, v2) == -1) continue;

        const bool point_left = Segment{v0, v}.face_left() || Segment{v, v2}.face_left();
        if (wall.face_right() && !point_left) continue;

        const bool point_right =
            Segment{v0, v}.face_right() || Segment{v, v2}.face_right();
        if (wall.face_left() && !point_right) continue;

        double x = wall.horizontal_distance(v);

        x = right ? x : -x;
        if (EPS < x && x < max_shift - EPS) shifts.push_back(x);
      }
    }
  };

  collect_shifts(polygon1, polygon2, true);
  collect_shifts(polygon2, polygon1, false);

  sort(shifts.begin(), shifts.end());

  double prev_shift_x = 0;
  double res = 0;

  for (const double x : shifts) {
    if (x - prev_shift_x < 0.1) continue;
    for (Point& p : polygon1) p.x += x - prev_shift_x;

    if (!intersection(polygon1, polygon2))
      res = max(res, common_boundary_length(polygon1, polygon2));

    prev_shift_x = x;
  }

  return res;
}

int main() {
  int N;

  while (cin >> N) {
    vector<Point> polygon1(N);
    for (int i = 0; i < N; i++) cin >> polygon1[i].x >> polygon1[i].y;
    cin >> N;
    vector<Point> polygon2(N);
    for (int i = 0; i < N; i++) cin >> polygon2[i].x >> polygon2[i].y;

    reverse(polygon1.begin(), polygon1.end());
    reverse(polygon2.begin(), polygon2.end());

    const auto rotations1 = create_rotations(polygon1, true);
    const auto rotations2 = create_rotations(polygon2, false);

    double ans = 0;

    vector<double> base2(rotations2.size());

    for (int i = 0; i < (int)polygon2.size(); i++) {
      const vector<Point>& polygon = rotations2[i];
      base2[i] = polygon[i].dist(vertex_at(polygon, i + 1));
    }

    for (int i = 0; i < (int)rotations1.size(); i++) {
      const double base1 = rotations1[i][i].dist(vertex_at(rotations1[i], i - 1));

      for (int j = 0; j < (int)rotations2.size(); j++) {
        ans = max(ans, optimal_shift(rotations1[i], rotations2[j], base1, base2[j]));
      }
    }

    cout << fixed << setprecision(12) << ans << endl;
  }
}