#P3415. Altar Location with Maximum Barrier Layers

    ID: 16670 Type: Default 1000ms 256MiB

Altar Location with Maximum Barrier Layers

Altar Location with Maximum Barrier Layers

In the Dgeak continent, the landscape is modeled as an infinite Cartesian plane where there are n crystal pillars (called Swaryea pillars), each represented by a point with integer coordinates. A set of four distinct pillars can form a magical barrier (or "结界") if they can be connected in order to form a quadrilateral whose two diagonals are parallel to the x‐axis and y‐axis respectively, and the intersection point of these diagonals (called the center of the barrier) lies strictly inside the quadrilateral (i.e. not on its boundary). A natural way to realize such a barrier is to have the four vertices positioned at

[ \begin{cases} A = (u - a,, v),\ B = (u,, v + b),\ C = (u + a,, v),\ D = (u,, v - b), \end{cases} ]

with (a>0) and (b>0). Notice that the diagonals are (AC) (horizontal) and (BD) (vertical) whose intersection is ((u,v)).

Barriers can be nested to provide multiple layers of protection. More precisely, a set of barriers sharing the same center can form multiple layers if their boundaries do not touch each other (i.e. for any two barriers corresponding to parameters ((a_1,b_1)) and ((a_2,b_2)) with (a_1 < a_2) and (b_1 < b_2), the inner barrier is strictly contained in the outer one). However, the center itself must not contain a crystal pillar. For each potential center, the maximum possible number of disjoint (nested) barrier layers is (\min(H, V)), where (H) is the number of distinct horizontal pairs of pillars forming candidates (i.e. pairs on the same horizontal line that yield a value of (a)) and (V) is the number of distinct vertical pairs (pairs on the same vertical line that yield a value of (b)).

Your task is to determine:

  1. The maximum number of barrier layers (i.e. the highest (\min(H, V))) among all possible valid centers (that do not coincide with any pillar).
  2. The number of different valid center locations that achieve this maximum number of layers.

Input Format:
The first line contains an integer (n) (the number of crystal pillars). Each of the next (n) lines contains two space‐separated integers (x) and (y), representing the coordinates of a crystal pillar.

Output Format:
Output two integers separated by a space: the maximum number of barrier layers and the number of altar (center) locations that achieve this maximum. If no valid center exists (i.e. no barrier can be formed), output "0 0".

Note:
A barrier using pillars at ((u - a, v)), ((u, v + b)), ((u + a, v)), and ((u, v - b)) is valid only if (a > 0,\ b > 0), and the center ((u,v)) does not lie on any pillar.

inputFormat

The first line contains an integer n (the number of crystal pillars). Then n lines follow, each containing two space‐separated integers x and y representing the coordinates of a pillar.

outputFormat

Output two integers separated by a space: the maximum number of barrier layers that can protect an altar and the number of altar locations (i.e. centers) that achieve this maximum. If no valid center exists, output "0 0".

sample

4
0 0
2 0
0 2
2 2
0 0