Construct The Parameter

Ninja
0/200
Average time to solve is 40m
profile
Contributed by
7 upvotes
Asked in companies
Google incCodenation

Problem statement

You are given a set of ‘N’ distinct points on a 2-D plane. You have to construct the smallest parameter that contains all points of the given set. You have to print all the points that lie on the smallest parameter.

For example:

For the points given below.


The smallest parameter that contains all the points will look like the diagram given below.

Detailed explanation ( Input/output format, Notes, Images )
Input Format- 
First-line contains ‘T’, denoting the number of Test cases.
For each Test case:
The first line contains an integer, ‘N’, denoting the number of points on the 2-D plane.
The following ‘N’ line contains two space-separated integers, denoting the x coordinate and y coordinate of the point.
Output Format- 
For each test case, print ‘X’ lines, where ‘X’ is the number of distinct points on the smallest parameter. In each line, you have to print two space-separated integers denoting the point's x coordinate and y coordinate.
Note : 
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints - 
1 <= ‘T’ <= 5
3 <= ‘N’ <= 10^5 
0 <= ‘x’ & ‘y’ <= 10^9.
Note- Sum of ‘N’ over all test cases does not exceed 10^5.

Time Limit: 1 sec
Sample Input-1
2
3
1 1
2 2
1 3
4
1 1
3 3
4 1
3 2
Sample Output-1
1 1
2 2
1 3
1 1
3 3
4 1
Explanation for Sample Input 1:
For test case 1:
    All the points form a triangle, so we have to take all of them.
For test case 2:


From the image, we can see the smallest parameter.
Sample Input -2
2
4
1 1
2 2
3 3
4 4
4
1 1
1 2
2 2
2 1
Sample Output -2
1 1
2 2
3 3
4 4
1 1
1 2
2 2
2 1
Hint

Try using some convex-hull techniques.

Approaches (1)
Monotone Chain algorithm

Approach: We will use the Monotone Chain algorithm to construct the convex hull. The algorithm first locates the leftmost and rightmost points and then constructs the convex hull in two parts: first, the upper hull and then the lower hull. We sort the points for the upper hull, then go through the points and add each point to the hull. Always after adding a point to the hull, we make sure that the last line segment in the hull does not turn left. As long as it turns left, we repeatedly remove the second last point from the hull. The following pictures show how the Monotone Chain algorithm works for the example given in the problem to find the upper parameter/hull:

                   

To get the lower hull, we will repeat the same steps as we did to get the upper hull. 

Algorithm: 

  • Func cross(p, q, r).
    • Create a variable ‘ax’ and initialize it to r[0] - p[0].
    • Create a variable ‘ay’ and initialize it to r[1] - p[1].
    • Create a variable ‘bx’ and initialize it to q[0] - p[0].
    • Create a variable ‘by’ and initialize it to q[1] - p[1].
    • Return ax * by - ay * bx.
  • Func Main().
    • Create two vectors, ‘up’, ‘down’.
    • Sort Points.
    • Append the first two points in ‘up’.
    • Iterate using a for loop from i = ‘2’ to ‘N - 1’.
      • While the size of ‘up’ is greater than 1.
        • Create a variable ‘m’ and initialize it to the size of ‘up’.
        • If cross(up[m - 1], up[m - 2], Points[i]) > 0.
          • Remove the last point from ‘up’.
        • Else.
          • Break.
      • Append Points[i] in ‘up’.
    • Append the last two points in ‘down’.
    • Iterate using a for loop from i = ‘N - 3’ to ‘0’.
      • While the size of ‘down’ is greater than 1.
        • Create a variable ‘m’ and initialize it to the size of ‘down’.
        • If cross([down[m - 1], down[m - 2], Points[i]) > 0.
          • Remove the last point from ‘down’.
        • Else.
          • Break.
      • Append Points[i] in ‘down’.
    • Print all the distinct values that are present in ‘up’ and ‘down’.
Time Complexity

O(N * log(N)), where ‘N’ is the number of points.

We are sorting all the ‘N’ Points. Hence the overall complexity is O(N * log(N)).

Space Complexity

O(N), where ‘N’ is the number of points.

We may store all of the ‘N’ points. Hence the overall complexity is O(N).

Code Solution
(100% EXP penalty)
Construct The Parameter
Full screen
Console