ECOO '18 R2 P4 - Three Squares

View as PDF

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 N 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 L be the side length of the squares. What is the minimum possible value of L such that all the points can be covered?

Input Specification

The standard input will contain 10 datasets. Each dataset begins with an integer N (4 \le N \le 100\,000). The next N lines each contain two integers X, Y (-10^9 \le X,Y \le 10^9), the points in the plane.

For the first 4 cases, N \le 30.

Output Specification

For each dataset, output the value of L.

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

There are no comments at the moment.