Submit solution

Points:
15 (partial)

Time limit:
13.0s

Memory limit:
128M

Problem type

Allowed languages

Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, ~~CommonLisp~~, D, Dart, F#, Forth, Fortran, Go, ~~Groovy~~, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, ~~Nim~~, ~~ObjC~~, OCaml, ~~Octave~~, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Given distinct points on a 2D plane, you would like to place three identical, axis-aligned squares on the plane such that every point is either inside or on the border on one of the squares.

Let be the side length of the squares. What is the minimum possible value of such that all the points can be covered?

#### Input Specifications

The standard input will contain 10 datasets. Each dataset begins with an integer . The next lines each contain two integers , , the points in the plane.

For the first 4 cases, .

#### Output Specifications

For each dataset, output the value of .

#### Sample Input (Two Datasets Shown)

```
4
1 1
2 2
3 3
4 4
5
1 1
2 1
-2 -1
4 4
-4 -2
```

#### Sample Output

```
1
2
```

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org

## Comments