Problem J5: Square Pool

Problem DescriptionCopy Anchor Link

Ron wants to build a square pool in his square $N$-by-$N$ yard, but his yard contains $T$ trees. Your job is to determine the side length of the largest square pool he can build.

Input SpecificationCopy Anchor Link

The first line of input will be an integer $N$ with $N\geq2$. The second line will be the positive integer $T$ where $T < N^2$. The remaining input will be $T$ lines, each representing the location of a single tree. The location is given by two positive integers, $R$ and then $C$, separated by a single space. Each tree is located at row $R$ and column $C$ where rows are numbered from top to bottom from $1$ to $N$ and columns are numbered from left to right from $1$ to $N$. No two trees are at the same location.

The following table shows how the available 15 marks are distributed.

Output SpecificationCopy Anchor Link

Output one line containing $M$ which is the largest positive integer such that some $M$-by-$M$ square contained entirely in Ron’s yard does not contain any of the $T$ trees.

Sample Input 1Copy Anchor Link

5 
1 
2 4

Output for Sample Input 1Copy Anchor Link

3

Explanation of Output for Sample Input 1Copy Anchor Link

A picture of the yard is below. The location of the tree is marked by and one of several $3$-by-$3$ squares that do not contain the tree is highlighted. All larger squares contain a tree.

Sample Input 2Copy Anchor Link

15 8 4 7 4 1 14 11 10 6 13 4 4 10 10 3 9 14

Output for Sample Input 2Copy Anchor Link

7

Explanation of Output for Sample Input 2Copy Anchor Link

A picture of the yard is below. The location of each tree is marked by and one of several $7$-by-$7$ squares that do not contain a tree is highlighted. All larger squares contain a tree.