#P3415. Altar Location with Maximum Barrier Layers
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:
- 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).
- 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