CTU Open Contest 2017 - Equinox Roller Coaster

View as PDF

Points: 15
Time limit: 7.0s
Memory limit: 256M

Problem type

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 specifying the number of stable grid points . Next, there are lines each of which specifies - and -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 .

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
0 0
0 1
1 0
8
0 10
0 20
0 30
10 0
10 10
10 20
20 0
20 10

Sample Output

0
10