Dadasquare

Binary-search the minimum feasible square side length $L$. Since all point coordinates are integers, every partition of the points into four squares admits squares with integer-aligned sides; hence the optimal $L$ is an integer in the range $[0,2\cdot 10^9]$.

Let the bounding box of all points be $[x_{\min},x_{\max}]\times[y_{\min},y_{\max}]$.

1. A square occupies a corner.

If two squares suffice, there is a solution with the squares anchored at opposite corners of the bounding box. Checking both diagonals takes $O(N)$.

If three squares suffice, one square can be anchored at a corner: four extreme sides must be touched by three squares, so a square touches two extremes. For adjacent extremes, move the square to their common corner. For opposite extremes, the corresponding total extent is at most $L$, allowing an equivalent corner placement. Try all four corners and solve the residual two-square problem in $O(N)$ total time.

Likewise, if any square in a four-square cover touches two extreme sides, a corner square can be chosen. Try the four corners and solve the residual three-square problems in $O(N)$ total time.

2. Four squares touch four different sides.

Otherwise the four squares individually touch the left, right, top, and bottom sides. Denote them by $S_L,S_R,S_T,S_B$. Anchor their corresponding edges at . By also checking the instance reflected vertically, it suffices to consider the case where lies to the left of .

Fix the height $t$ of the upper edge of $S_L$. Of the points not covered by $S_L$, let $a$ be the minimum -coordinate. We may anchor the left edge of at , with its upper edge at . This is a greedy placement: moving left until it reaches the leftmost remaining point cannot lose any point needed by the subsequent squares.

Next, let $b$ be the minimum $x$-coordinate among points still uncovered. Place $S_B$ with left edge $b$ and bottom edge at $y_{\min}$. The remaining points must fit inside a single square, which is equivalent to requiring both extents of their bounding box to be at most .

3. An $O(N\log N)$ sweep.

Only points with $x_i\le x_{\min}+L$ can be covered by $S_L$. Such a point belongs to exactly when , yielding at most two events per point.

The vertical coverage ranges of $S_T$ and $S_B$ are fixed: respectively $y\ge y_{\max}-L$ and within the bounding box. Classify every point by membership in the top range, bottom range, both, or neither.

Sort the points by $x$ and build a segment tree. For the points currently outside $S_L$, every node stores a bounding box separately for each of these four classes. Changing the activity of one point takes $O(\log N)$. Querying the bounding box of a union of classes restricted to an $x$-interval also takes .

The current left edge $a$ of $S_T$ is the minimum $x$ among active points. $S_T$ removes top-range points with . The next minimum remaining is , the left edge of .

All points surviving $S_T$ and $S_B$ have $x\ge b$. Their bounding box is the union of three queries:

• $b\le x\le a+L$: points in neither the top nor the bottom range.
• $\max(b,a+L+1)\le x\le b+L$: points not in the bottom range.

The boundaries use integer coordinates, so strict inequalities can be expressed by adding one. At each event height, test the state after activating the newly covered points, and also the state immediately after points leave the square. Thus all distinct active sets are considered.

There are at most $2N$ events, each requiring $O(\log N)$ time for updates and a constant number of queries. The sweep takes $O(N\log N)$ time. Reflection changes this only by a constant factor.

Each feasibility test takes $O(N\log N)$ time. Binary search gives $O(N\log N\log 10^9)$ total time and $$ space.