Symmetric Boundary (Problem I, The 2024 ICPC Asia Pacific Championship, 2024)
Time limit: 4 sec
Author: Mitsuru Kusumoto

# Problem Statement

Symmetrical figures are beautiful—and they are the subject of this task. A region in a 2D plane is _convex_ if, for every pair of points $p$ and $q$ in the region, the segment connecting $p$ and $q$ is entirely included in the region. Also, a region in a 2D plane is _point-symmetric_ if, when you rotate the region by 180 degrees around a certain point, the rotated region exactly matches the original region.

You are given a convex polygon in a 2D plane with $n$ vertices, numbered from $1$ to $n$ in counterclockwise order. Vertex $i$ has coordinates $(x_i, y_i)$. No three vertices are collinear. Determine whether there exists a convex, point-symmetric region containing all of the $n$ vertices on its boundary. If one or more such regions exist, compute the minimum area among all of them.

# Input

The first line of input contains one integer $n$ ($3 \leq n \leq 30$). Each of the next $n$ lines contains two integers. The $i$-th line contains $x_i$ and $y_i$ ($0 \leq x_i, y_i \leq 1000$).

It is guaranteed that the given polygon is convex, its vertices are given in counterclockwise order, and no three of its vertices are collinear.

# Output

If one or more such regions exist, output the minimum area among all of them. The relative error of the output must be within $10^{-9}$.

If such a region does not exist, output $-1$ instead.

# Sample Input #1
```
4
0 0
10 0
8 9
4 9
```
# Sample Output #1
```
90.0
```
# Sample Input #2
```
8
8 10
2 9
0 8
0 2
2 0
8 0
10 2
10 8
```
# Sample Output #2
```
-1
```
# Sample Input #3
```
6
231 77
359 20
829 124
998 461
941 735
879 825
```
# Sample Output #3
```
486567.9669655848
```
# Explanation for the sample input/output

Figure I.1 illustrates the vertices in the sample input as black dots. For sample inputs #1 and #3, the shaded regions represent the regions with the minimum possible area.

![Figure I.1: Illustrations of the sample inputs (from left to right).](icpc-apac-2024-symmetric-1.png)

Sample inputs:
4
0 0
10 0
8 9
4 9

8
8 10
2 9
0 8
0 2
2 0
8 0
10 2
10 8

6
231 77
359 20
829 124
998 461
941 735
879 825

Sample outputs:
90.0

-1

486567.9669655848

# Solution Analysis
Analysis author: Mitsuru Kusumoto

Let’s denote an input point $(x_i, y_i)$ by $P_i$. Also, let $X$ represent the center of the point symmetry. According to the definition of point symmetry, a point $Q_i$ satisfying $(P_i + Q_i)/2 = X \Rightarrow Q_i = 2X - P_i$ should also be included in the boundary of the convex region we are seeking. The problem is to find a point $X$ such that the $2n$ points $P_1, \dots, P_n, Q_1, \dots, Q_n$ form a hull, meaning that the boundary of the convex hull of the $2n$ points contains all of them. We say that a point $X$ satisfying this condition is _valid_.

Somewhat briefly, the solution is as follows: for two indices $a$ and $b$ that are between 1 and $n$, inclusive, let $L(a,b)$ be a line passing through $(P_a + P_b)/2$ and $(P_{a+1} + P_b)/2$. Here, we say $P_{n+1} = P_1$. Draw $n^2$ lines of $L(a,b)$ on the plane for $1 \le a, b \le n$. There are $O(n^4)$ intersection points between the lines. For each intersection point, verify whether the point is valid or not. If it is valid, calculate the area of the hull. This process requires $O(n \log n)$ time for each intersection point. The minimum area found by this procedure represents the solution. The runtime complexity is $O(n^5 \log n)$.

But why is the above solution correct? Before delving into the rationale, let’s explain a few concepts.

- The point $Q_i$ depends on the point $X$, so from now on, we write $Q_i$ as $Q_i(X)$.
- For three points $A, B$ and $C$, let $CCW(A, B, C)$ be true if and only if $(B - A) \times (C - A) \ge 0$.
- For a valid point $X$, let $s(X)$ denote the area of a convex hull formed by the points $P_1, \dots, P_n, Q_1(X), \dots, Q_n(X)$.

When we draw $n^2$ lines, the plane is divided into $O(n^4)$ connected regions. Let’s select one region $R$. Here, $R$ includes the boundary of the region. We denote the interior points of $R$ by $R^\circ$. For any two points $X \in R^\circ$ and $X' \in R$, and for any two indices $a$ and $b$, both of the following hold.

- If $CCW(P_a, P_{a+1}, Q_b(X))$ is true, $CCW(P_a, P_{a+1}, Q_b(X'))$ is also true.  
  _(Hint: prove that $CCW(P_a, P_{a+1}, Q_b(X))$ is equivalent to $CCW((P_a + P_b)/2, (P_{a+1} + P_b)/2, X)$.)_

- If $CCW(P_a, Q_b(X), Q_{b+1}(X))$ is true, $CCW(P_a, Q_b(X'), Q_{b+1}(X'))$ is also true.

This implies that if one point in $R^\circ$ is valid, then any point in $R$ is valid. Also, the order of vertices on the boundary of a convex polygon formed by $P_1, \dots, P_n, Q_1(X), \dots, Q_n(X)$ is always the same for $X \in R$.

From this, we can deduce that the function $s : \mathbb{R}^2 \to \mathbb{R}$ is a linear function when the domain is restricted in $R$, because the area of a polygon is the sum of the cross product of neighboring vertices,

- $P_a \times P_{a+1}$ is constant,
- $P_a \times Q_b(X)$ and $Q_b(X) \times P_a$ vary linearly with respect to $X$, and
- $Q_b(X) \times Q_{b+1}(X) = (2X - P_b) \times (2X - P_{b+1}) = 2X \times (P_b - P_{b+1}) + P_b \times P_{b+1}$ **varies linearly with respect to $X$**.

Therefore, the minimum value of $s$ within the domain of $R$ is always achieved on the boundary of $R$. Specifically, since $R$ is a convex polygon, the minimum value is attained at the vertices of the region. This justifies the fact that we only need to check the intersection points of $n^2$ lines.

Special judge (C++ scorer):
#include <fstream>
#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cmath>
#include <cstdarg>

using ld = long double;

std::ifstream judgein, judgeans, conans;
FILE *judgemessage = NULL;
FILE *diffpos = NULL;
int judgeans_pos, con_pos;
int judgeans_line, con_line;

void ac() {
  puts("AC");
  exit(0); 
}

void wa() {
  puts("WA");
  exit(0);
}

void wrong_answer(const char *err, ...) {
  va_list pvar;
  va_start(pvar, err);
  vfprintf(stderr, err, pvar);
  fprintf(stderr, "\n");
  wa();
}

void judge_error(const char *err, ...) {
  va_list pvar;
  va_start(pvar, err);
  // If judgemessage hasn't been set up yet, write error to stderr
  if (!judgemessage) judgemessage = stderr;
  vfprintf(judgemessage, err, pvar);
  fprintf(judgemessage, "\n");
  assert(!"Judge Error");
}

bool isfloat(const char *s, ld &val) {
  char trash[20];
  ld v;
  if (sscanf(s, "%Lf%10s", &v, trash) != 1) return false;
  val = v;
  return true;
}

template <typename Stream>
void openfile(Stream &stream, const char *file, const char *whoami) {
  stream.open(file);
  if (stream.fail()) {
    judge_error("%s: failed to open %s\n", whoami, file);
  }
}

FILE *openfeedback(const char *feedbackdir, const char *feedback, const char *whoami) {
  std::string path = std::string(feedbackdir) + "/" + std::string(feedback);
  FILE *res = fopen(path.c_str(), "w");
  if (!res) {
    judge_error("%s: failed to open %s for writing", whoami, path.c_str());
  }
  return res;
}

const char *USAGE = "Usage: %s judge_in judge_ans contestant_ans";

int main(int argc, char **argv) {
  if(argc < 4) {
    judge_error(USAGE, argv[0]);
  }
  openfile(judgein, argv[1], argv[0]);
  openfile(judgeans, argv[2], argv[0]);
  openfile(conans, argv[3], argv[0]);

  constexpr ld float_rel_tol = 1e-9;

  ld jval;
  if (!(judgeans >> jval)) {
    judge_error("No answer given from judge!\n");
  }
  std::string team;
  if (!(conans >> team)) {
    wrong_answer("No answer given.\n");
  }

  if (jval < 0) {
    if (team != "-1") {
      wrong_answer("-1 is expected. output: %s\n", team.c_str());
    }
  } else {
    ld tval;
    if (!isfloat(team.c_str(), tval)) {
      wrong_answer("Not a float. output: %s\n", team.c_str());
    }
    constexpr ld eps = 1e-6;
    if (!(fabs(jval - tval) <= (1 + eps)*float_rel_tol*fabs(jval))) {
      wrong_answer("Too large difference.\n Judge: %.14Lf\n Team: %s\n Difference: %.14Lf\n", 
          jval, team.c_str(), jval - tval);
    }
  }

  if (conans >> team) {
    wrong_answer("Trailing output:\n%s", team.c_str());
  }

  ac();
}