## CCC '22 J5 - Square Pool

View as PDF

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 1G

Problem types
##### Canadian Computing Competition: 2022 Stage 1, Junior #5

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

#### Input Specification

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

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

Marks AwardedLength/Width of YardNumber of Trees
marks
marks
marks
marks

#### Output Specification

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

#### Sample Input 1

5
1
2 4

#### Output for Sample Input 1

3

#### Explanation of Output for Sample Input 1

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

#### Sample Input 2

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

#### Output for Sample Input 2

7

#### Explanation of Output for Sample Input 2

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