DIFFICULTY: MEDIUM-HARD
PREREQUISITES: Divide and Conquer, Convex Hull, Coordinate Geometry
PROBLEM:
Mr. X is the general secretary of the club, ‘Avengers’. Tomorrow there will be a fair in the club premises. He has N no. of volunteers with him. Each volunteer is sitting at a stall and also no two volunteers can sit at a single stall. Mr. X wants to communicate only with the volunteers at the boundary stalls. He knows the locations of all the stalls. But tomorrow he will be so busy with the event that he will have no time to communicate with all the volunteers. Interestingly, Mr. X was a computer engineer by profession. So, he selects out the minimum number (say, K ≤ N) of stalls at the boundary in such a way that the K number of stalls form a polygon and all the other stalls, if any, remain inside the polygon. He will communicate only with the volunteers at those selected K number of stalls at the boundary and those volunteers will be responsible to communicate with the rest of the volunteers at the stalls inside the boundary. After selecting the minimum number of stalls at the boundary, Mr. X will do the following task –
Out of the selected K number of stalls at the boundary Mr. X will select the coordinators from the stalls at the intersecting points of the boundary lines of the polygon in such a way that no two coordinators can be there on the same boundary line. Say, the number of the coordinators is C (C < K).
Input:
The first line contains an integer, T representing the number of test cases. Then the test cases will follow. The first line of each test case contains an integer, N representing the number of volunteers. Then each of the next N number of lines contains two integers separated by a whitespace for representing the x-coordinate (x) and the y-coordinate (y), respectively of the location of the stall.
Output:
In the output there is a single line for each of the T number of test cases. Each line contains two integers separated by a whitespace for representing the minimum number of volunteers, K and the number of coordinators, C.
Constraints
1 ≤ T ≤ 500
3 ≤ N ≤ 105
0 ≤ x, y ≤ 105
There must be at least three stalls which are not on the same line.
Example:
Input:
2
4
1 6
3 6
2 4
2 5
5
2 3
2 1
5 1
5 3
3 2
Output:
3 1
4 2
EXPLANATION:
Hence the first line of Input contains 2, meaning that there are two test cases. The second line says that there are four volunteers, i.e., there are four stalls for the first test case. So, each of the next four lines represents the coordinates of each of the four stalls. Out of the four, minimum three stalls are at the boundary to form a polygon (triangle here). The coordinates of the three stalls are (1, 6), (3, 6) and (2, 4). The stall with coordinates (2, 5) lies inside the triangle. So, K = 3 here. Now, if the volunteer at the stall with the coordinates (1, 6) is selected as the coordinator, the volunteer at (3, 6) can not be a coordinator because (1, 6) and (3, 6) lie on the same boundary line of the triangle. Similarly, the volunteer at (2, 4) can not be a coordinator because (1, 6) and (2, 4) lie on the same boundary line of the triangle. So, C = 1 here. If any other volunteer at the boundary is selected as the coordinator first, also the same thing will happen. That is, C = 1 in that case also. Since there are two test cases, in Output there will be two lines. The first line of Output will contain 3 and 1 separated by a white space, representing the values of K and C, respectively.
For selecting ‘K’ number of stalls which are only at the boundary, we need to find the convex hull for all the stalls. The convex hull is the smallest convex polygon where ‘K’ number of points will lie on the polygon boundary and the rest of the points, i.e., ‘N-K’ number of points will strictly lie inside the polygon. That means, ‘K’ should be the minimum number of stalls out of ‘N’ number of stalls. Just like a convex hull, there can be two or more number of stalls on a boundary line of the convex polygon.
Now, only the stalls at the intersecting points of the boundary lines of the polygon will be selected as the coordinators. If one stall at the intersecting point of any two boundary lines is selected as a coordinator, no other stalls lying on these two boundary lines can not be selected as the coordinators. ‘C’ is the number of the selected coordinators. In the problem it has not been stated to minimize C. Also there is no relationship between ‘K’ and ‘C’. But for a given ‘N’ number of stalls with the given locations, the values for ‘K’ and ‘C’ are unique. You need to find out ‘C’ based on the condition that no two coordinators can be there on the same boundary line.
The seventh line of Input says that there are five volunteers, i.e., there are five stalls for the second test case. So, each of the next five lines represents the coordinates of each of the five stalls. Hence, minimum four stalls are at the boundary to form a polygon (rectangle here). The coordinates of the four stalls are (2, 1), (2, 3), (5, 1) and (5, 3). The stall with the coordinates (3, 2) lies inside the rectangle. So, K = 4 here. Applying the same logic as in the previous test case, only two volunteers can be selected as the coordinators. So, C = 2 here. The second line of Output will contain 4 and 2 separated by a white space, representing the values of K and C, respectively.
For selecting ‘K’ number of stalls which are only at the boundary, we need to find the convex hull for all the stalls. The convex hull is the smallest convex polygon where ‘K’ number of points will lie on the polygon boundary and the rest of the points, i.e., ‘N-K’ number of points will strictly lie inside the polygon. That means, ‘K’ should be the minimum number of stalls out of ‘N’ number of stalls. Just like a convex hull, there can be two or more number of stalls on a boundary line of the convex polygon.
Now, only the stalls at the intersecting points of the boundary lines of the polygon will be selected as the coordinators. If one stall at the intersecting point of any two boundary lines is selected as a coordinator, no other stalls lying on these two boundary lines can not be selected as the coordinators. ‘C’ is the number of the selected coordinators. In the problem it has not been stated to minimize ‘C’. Also there is no relationship between ‘K’ and ‘C’. But for a given ‘N’ number of stalls with the given locations, the values for ‘K’ and ‘C’ are unique. You need to find out ‘C’ based on the condition that no two coordinators can be there on the same boundary line.
Test cases:
A.
Input :
1
6
5 8
6 7
8 6
9 8
8 9
6 9
Output :
6 3
B.
Input :
1
3
6 2
8 2
7 4
Output :
3 1
C.
Input :
1
4
1 7
4 7
1 10
4 10
Output :
4 2
D.
Input :
1
6
4 2
5 1
8 1
7 3
5 4
6 2
Output :
5 2
E.
Input :
1
7
1 6
5 5
7 8
6 9
3 8
6 6
4 7
Output :
6 3