I  Symmetric Boundary

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 \iff 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, \ldots, P_n, Q_1, \ldots, 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, \ldots, P_n, Q_1(X), \ldots\), \(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, \ldots, P_n, Q_1(X), \ldots, 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.