Last Updated: 28 Nov, 2021

Construct The Parameter

Ninja

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 Approach

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’.

Solve now