Czech ACM Student Chapter

Czech Technical University in Prague

Charles University in Prague

Technical University of Ostrava

ˇ

Slovak University of Technology

University of Zilina

Masaryk University

University of West Bohemia

CTU Open Contest 2017

Equinox Roller Coaster

equiroaster.c, equiroaster.cpp, equiroaster.c11, Equiroaster.java, equiroaster.py

Equiroaster is an abbreviation of EQUInox ROller coASTER, a new and grand attraction which

is going to be built in the park vicinity the next year.

The name of the roller coaster comes from the fact that it is the first roller coaster of its class

with a construction and shape directly linked to major astronomical events. Twice a year, at

equinox, the visitors will enjoy an unforgettable ride enhanced by additional visual effects. Also,

the advertising value of equinox rides is expected to be very high.

To meet the expectations, Equiroaster must be built very precisely. The alignment of its tracks

with East-West direction must be precise. The tracks will be supported by four main piers and

the alignment of the Southern and the Northern pair of piers with East-West direction must be

equally precise.

Equiroaster will be built in the field close to other park attractions. The field geology is suspected

to be somewhat less favorable to large building projects and thus a detailed survey of the field

was commissioned. A grid perfectly aligned with East-West direction (or equivalently, with

North-South direction) and with grid points one meter apart was projected onto the field. Each

grid point was geologically evaluated and marked as stable or unstable.

All four main piers of Equiroaster must be built on stable grid points. It is hoped that there

are enough stable grid points in the field to allow for a really extensive design of the coaster.

However, the building technology dictates that the base of the four main piers must form a

perfect square in order to reliably support the massive weight of the coaster.

The task is to determine the maximum possible distance between the piers on one side of the

coaster according to the specifications described above.

Input Specification

There are more test cases. Each case starts with a line containing one integer N specifying the

number of stable grid points (1 ≤ N ≤ 100 000). Next, there are N lines each of which specifies

x- and y-coordinates of a grid point. You should suppose that the grid axes are aligned with

East-West and with South-North directions and also that the coordinates are given in whole

meters. All grid points in one test case are unique. The absolute value of each coordinate is at

most 109.

Output Specification

For each test case, print a single line with one integer denoting the maximum possible distance

in meters between the centers of two piers on one side of the coaster. If it is not possible to

place the piers on stable grid points according to the specifications, print 0 on the output line.

Sample Input

3

00

01

10

8

0 10

0 20

0 30

10 0

10 10

10 20

20 0

20 10

Output for Sample Input

0

10