Description

The continent of Dgeak can be regarded as a vast plane represented by a Cartesian coordinate system. On this plane, there are n Swaryea crystal pillars, each represented by a point.

If 4 crystal pillars, connected in order, form a quadrilateral such that its two diagonals are respectively parallel to the x-axis and the y-axis, and the intersection of the diagonals lies strictly inside the quadrilateral (not on the boundary), then these 4 pillars can form a ward. The intersection of the diagonals is called the center of this ward.

For example, in the left figure below, pillars A, B, C, D can form a ward, whose center is O.

To best resist Dar-dzo-nye, people will place the altar at a location enclosed by the most layers of wards. These different layers must share the same center, their boundaries must be pairwise disjoint, and there must be no crystal pillar at the center. The number of wards sharing the same center is called the number of layers.

To achieve this, people will first use the existing crystal pillars to form several wards, and then build altars at the centers of some wards.

For example, in the top-right figure, black dots are crystal pillars (note that points P and O are not crystal pillars). One optimal location is point O, where an altar can be placed within 3 layers of wards; a specific scheme is shown in the bottom-left figure. Of course, the optimal location is not necessarily unique; in the top-right figure, the point P that is 1 unit to the left of O can also host an altar within 3 layers of wards, as shown in the bottom-right figure.

Now people want to know:

1. The number of layers at the best altar location.
2. How many optimal locations there are.

Input Format

The first line contains one positive integer n, the number of crystal pillars. Each of the next n lines contains two non-negative integers x, y, the coordinates of a crystal pillar. It is guaranteed that there are no duplicate coordinates.

Output Format

The first line contains one integer, the maximum number of layers in which an altar can be located. The second line contains one integer, the number of locations that achieve this maximum.

26
0 5
1 1
1 5
1 9
3 5
3 10
4 0
4 1
4 2
4 4
4 6
4 9
4 11
5 0
5 2
5 4
5 8
5 9
5 10
5 11
6 5
7 5
8 5
9 10
10 2
10 5

3
2

Hint

Constraints:

• For 30% of the testdata, $n \le 1000$.
• For another 30% of the testdata, $n \le 10000$.
• For the remaining 40% of the testdata, $n \le 100000$.
• It is guaranteed that $0 \le x, y \le n$.

Translated by ChatGPT 5