Convex Hulk ( DSA INTERVIEW PREPARATION PROBLEMS AND SOLUTIONS )

 Hulk includes a set of distinct points P within the second plane. His signature move is Hulk Smash. He performed Hulk Smash on the set P that caused the points to alter, so he obtained a brand new set of points P′.

More formally, Hulk Smash makes the new set P′ within the following way:

Initially, let P′ be empty.
For every Pi and Pj specified 1≤i

Constraints

• 1≤T≤20$1\le T\le 20$
• 3≤N≤2⋅105$3\le N\le 2\cdot {10}^5$
• −5⋅108≤Pi.x,Pi.y≤5⋅108$-5\cdot {10}^8\le P_i.x,P_i.y\le 5\cdot {10}^8$
• The convex hull of the input set P$P$ has positive area
• Sum of N$N$ over all tests cases does not exceed 2⋅105$2\cdot {10}^5$

Subtasks

Subtask 1 (20 points):

• Sum of N$N$ over all test cases does not exceed 103${10}^3$

Subtask 2 (80 points):

• Original constraints

Sample Input 1 

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

Sample Output 1 

8
4

• Tweet
• Share
• Share
• Share
• Share

Related Post