Description

Translated from [CERC2018] Incredible Hull.

In a royal casino, there is a large room containing many slot machines. The casino owner feels that the room layout is too simple; as a result, gamblers have a good chance to leave the room before losing too much money. Since the room layout has to be fixed, the owner designed a complicated way to place the slot machines and build corridors, so that people are more likely to get lost inside.

The room is roughly elliptical in shape. If the room were empty, then from any point inside the room, the whole room would be visible. Each of the $N$ slot machines in the room can be treated as a point, and each has a special profit value; no two slot machines have the same profit value. The owner wants these slot machines to be connected by corridors in the following way.

At least three slot machines have already been built into the wall of the room. All of these wall machines must be directly connected with straight corridors, forming a closed perimeter cycle surrounding the entire room. All remaining slot machines are located strictly inside this closed perimeter cycle.

The room is to be subdivided into smaller regions by straight corridors, and each region is enclosed by its own perimeter cycle. The subdivision is performed in the following two steps.

• The first step works as follows. If the current perimeter cycle contains at least four slot machines, choose two slot machines as hubs. The first one is the slot machine on the perimeter cycle with the highest profit. The second one is also on the perimeter cycle and is farthest from the first hub slot machine. The distance between two slot machines along the perimeter cycle is defined as the number of corridor edges on the cycle that must be traversed to get from one to the other. If there are multiple farthest slot machines, then the second hub is the one with the highest profit among them. The region inside the perimeter cycle is split into two parts by adding a corridor connecting these two hubs. The perimeter cycle of each newly formed region consists of a part of the original perimeter cycle together with this new corridor. Repeat this process until no new region can be created.
• After the previous process finishes, the second subdivision process starts. It works as follows. For any region $A$ that has no corridors in its interior, consider all slot machines strictly inside that region. If there is at least one, then select the slot machine with the highest profit and build a corridor from it to every slot machine on the perimeter cycle $P_A$ of region $A$. This splits the region into several smaller regions. The perimeter cycle of each new region contains one edge from $P_A$ and two newly built corridors. Repeat this process until no new region can be created.

The casino owner wants to estimate the profit potential of his design. For this purpose, he defines a so-called high-profit configuration. This configuration is a largest possible set of slot machines such that any two slot machines in the set are directly connected by a corridor.

The owner is interested in three profit parameters. The first parameter is the size of a high-profit configuration, the second parameter is the number of high-profit configurations in this design, and the third parameter is the number of slot machines that belong to at least one high-profit configuration.

Input Format

The first line contains an integer $N$, the number of slot machines.

The next $N$ lines each contain two integers $X, Y$, describing the position of a slot machine in the room. All slot machines are given in decreasing order of profit value, and no three slot machines are collinear.

Output Format

Output the three profit parameters.

6
8 2
6 8
4 9
3 5
3 0
1 5

4 1 4

6
1 1
6 1
1 6
6 6
3 2
4 5

4 2 6

Hint

$3 \le N \le 10^5, 0 \le X, Y \le 10^9$.

Translated by ChatGPT 5