P10742 [SEERC 2020] Simple Hull

Gary created a polygon with $n$ points, where each point has coordinates of the form $(x,y)$. You need to add some edges so that all points are included, and the resulting graph is a "polygonal chain" (that is, each point can be connected to or be connected from at most $2$ points, and the drawn edges are allowed to intersect other edges in the graph). You also need to ensure that for every two points $i$ and $j$ that are connected by an edge, the edge formed by these two points is vertical or horizontal in the graph. Output the minimum possible area of the resulting graph.

The first line contains an integer $n\ (1 \leq n \leq 10^5)$, the number of points. Then follow $n$ lines, each containing two integers $x_i,y_i\ (1 \leq x_i,y_i \leq 10^6)$.

Output the area of the resulting $n$-gon.

The graphs drawn for the three samples are, in order:  (The above figures are not drawn to scale.) Translated by ChatGPT 5