Czech ACM Student Chapter
Czech Technical University in Prague
Charles University in Prague
Technical University of Ostrava
acm
ˇ
Slovak University of Technology
University of Zilina
cz
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
