407949: GYM102947 J Camping in the Wild

Akhil and his students are going camping! While his students are all merrily preparing for the outing, Akhil is more focused on the safety of the students. As such, he wants to bring a few more adults along with him on the trip to make sure that the students will not be put in danger.

At the campsite, all suitable camping sites are at lattice points on the 2D coordinate grid. This is to ensure that the tents will be easy to identify, and it ensures that the distance between tents will not to be little. However, there are some lattice points on the grid that instead of a camping set, where a watchtower has been put in place. These watchtowers are particularly advanced. If two watchtowers are occupied by teachers, then they will both be alerted if a student crosses the line segment with the two watchtowers as endpoints. However, if there exists a watchtower between two watchtowers such that all 3 towers are perfectly colinear, then a teacher is needed at all 3 if the desire is to watch the entire segment.

Once night comes, Akhil wants to make sure that no student can wander off from their tent into the wilderness without any adult being alerted via a watchtower. Such locations are deemed "safe" if there is some way of occupying 3 or more watchtowers such that a student at that spot cannot wander off infinitely in some direction without alerting a watchtower. Given the locations of the watchtowers, Akhil wants to determine the maximum number of students that can go on this camping trip. A student can go if there is an available "safe" camping spot (that is not occupied by a watchtower). Help Akhil find the maximum number of students that can safely go on the camping trip and the minimum number of adults required to ensure that all "safe" spots are indeed guarded.

The first line will contain $$$n (1 \le n \le 10^5)$$$, the number of watchtowers. Note that every lattice point that is not a watchtower is a viable camping spot.

The next $$$n$$$ lines will each contain a pair of integers $$$x_i, y_i (0 \le x_i, y_i \le 10^9)$$$, denoting the location of the $$$i^{th}$$$ watchtower.

Output two lines of output, with the first being the maximum number of "safe" students, and the second being the minimum number of adults needed to accommodate this maximum amount of students.

7
0 3
2 2
2 6
4 0
5 4
6 7
8 3

29
5

8
0 0
0 1
0 2
2 2
2 1
2 0
1 0
1 2

1
8