Problem

Submissions

Hints & solutions

Discuss

Construct The Parameter

Ninja

0/200

Average time to solve is 40m

Contributed by

7 upvotes

Asked in companies

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

Sample Output-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

Sample Output -2

Hint 1

Try using some convex-hull techniques.

Approaches (1)

Approach 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).

(100% EXP penalty)

Construct The Parameter

Raj Ghosh

Interview problems

JAVA SOLUTION || Construct The Parameter ||

import java.util.* ;

import java.io.*;

public class Solution

{

public static long cross(ArrayList<Integer> p, ArrayList<Integer> q, ArrayList<Integer> r)

{

long ax = (long)(r.get(0) - p.get(0));

long ay =(long)(r.get(1) - p.get(1));

long bx =(long)(q.get(0) - p.get(0));

long by =(long)(q.get(1) - p.get(1));

return (ax * by - ay * bx);

}

public static ArrayList<ArrayList<Integer>> construct(ArrayList<ArrayList<Integer>> Points)

{

Collections.sort(Points, new Comparator<ArrayList<Integer>>() {

public int compare(ArrayList<Integer> a, ArrayList<Integer> b) {

int la = a.size();

int lb = b.size();

int i=0,j=0;

while(i<la && j<lb){

if(a.get(i) == b.get(j))

{

i++;j++;

}else if(a.get(i) > b.get(j)){

return 1;

}else{

return -1;

}

return 0;

}

});

int n = Points.size();

ArrayList<ArrayList<Integer>> up = new ArrayList<ArrayList<Integer>>();

ArrayList<ArrayList<Integer>> down = new ArrayList<ArrayList<Integer>>();

up.add(Points.get(0));

up.add(Points.get(1));

for (int i = 2; i < n; i++)

{

while (up.size() >= 2)

{

int m = up.size();

if (cross(up.get(m - 1), up.get(m - 2), Points.get(i)) > 0)

{

int idx = m - 1;

up.remove(idx);

}

else

{

break;

}

up.add(Points.get(i));

}

down.add(Points.get(n - 1));

down.add(Points.get(n - 2));

for (int i = n - 3; i >= 0; i--)

{

while (down.size() >= 2)

{

int m = down.size();

if (cross(down.get(m - 1), down.get(m - 2), Points.get(i)) > 0)

{

int idx = down.size() - 1;

down.remove(idx);

}

else

{

break;

}

down.add(Points.get(i));

}

HashSet<ArrayList<Integer>> s = new HashSet<ArrayList<Integer>>();

ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();

for (ArrayList<Integer> i : up)

{

if (s.contains(i) == false)

{

ans.add(i);

s.add(i);

}

for (ArrayList<Integer> i : down)

{

if (s.contains(i) == false)

{

ans.add(i);

s.add(i);

}

Collections.sort(ans, new Comparator<ArrayList<Integer>>() {

public int compare(ArrayList<Integer> a, ArrayList<Integer> b) {

int la = a.size();

int lb = b.size();

int i=0,j=0;

while(i<la && j<lb){

if(a.get(i) == b.get(j))

{

i++;j++;

}else if(a.get(i) > b.get(j)){

return 1;

}else{

return -1;

}

return 0;

}

});

return ans;

}

4 views

0 replies

1 upvote

Alok Nayak

Interview problems

c++ solution



long long cross(vector<int> p, vector<int> q, vector<int> r)
{
    long long ax = r[0] - p[0];
    long long ay = r[1] - p[1];
    long long bx = q[0] - p[0];
    long long by = q[1] - p[1];
    return ax * by - ay * bx;
}


vector<vector<int>> construct(vector<vector<int>> Points)
{
    sort(Points.begin(), Points.end());
    int n = Points.size();

    vector<vector<int>> up, down;
    // Finding the upper hull/parameter.
    up.push_back(Points[0]);
    up.push_back(Points[1]);
    for (int i = 2; i < n; i++)
    {
        while (up.size() >= 2)
        {
            int m = up.size();
            // Checking if the point turned left or not.
            if (cross(up[m - 1], up[m - 2], Points[i]) > 0)
            {
                up.pop_back();
            }
            else
            {
                break;
            }
        }
        up.push_back(Points[i]);
    }
    // Finding the lower hull/parameter.
    down.push_back(Points[n - 1]);
    down.push_back(Points[n - 2]);
    for (int i = n - 3; i >= 0; i--)
    {
        while (down.size() >= 2)
        {
            int m = down.size();
            // Checking if the point turned left or not.
            if (cross(down[m - 1], down[m - 2], Points[i]) > 0)
            {
                down.pop_back();
            }
            else
            {
                break;
            }
        }
        down.push_back(Points[i]);
    }
    // Finding the distinct points in 'up' + 'down'.
    set<vector<int>> s;
    vector<vector<int>> ans;
    for (auto& i : up)
    {
        if (s.find(i) == s.end())
        {
            ans.push_back(i);
            s.insert(i);
        }
    }
    for (auto& i : down)
    {
        if (s.find(i) == s.end())
        {
            ans.push_back(i);
            s.insert(i);
        }
    }
    return ans;
}

66 views

0 replies

0 upvotes

Suchismita Behera

Interview problems

JAVA | C++ | Python Codes

JAVA

/*
    Time Complexity: O(N * log(N))
    Space Complexity: O(N)

    Where 'N' is the number of points.
*/

public class Solution 
{
	public static long cross(ArrayList<Integer> p, ArrayList<Integer> q, ArrayList<Integer> r)
	{
		
		long ax = (long)(r.get(0) - p.get(0));
		long ay =(long)(r.get(1) - p.get(1));
		long bx =(long)(q.get(0) - p.get(0));
		long by =(long)(q.get(1) - p.get(1));
		return (ax * by - ay * bx);
	}

	
    public static ArrayList<ArrayList<Integer>> construct(ArrayList<ArrayList<Integer>> Points)
	{

		Collections.sort(Points, new Comparator<ArrayList<Integer>>() {    
			public int compare(ArrayList<Integer> a, ArrayList<Integer> b) {
				int la = a.size();
				int lb = b.size();
				int i=0,j=0;
				while(i<la && j<lb){
					if(a.get(i) == b.get(j))
					{
						i++;j++;
					}else if(a.get(i) > b.get(j)){
						return 1;
					}else{
						return -1;
					}
				}
				return 0;
				
			}               
		});
		
		int n = Points.size();
	
		ArrayList<ArrayList<Integer>> up = new ArrayList<ArrayList<Integer>>();
		ArrayList<ArrayList<Integer>> down = new ArrayList<ArrayList<Integer>>();
		
		// Finding the upper hull/parameter.
		up.add(Points.get(0));
		up.add(Points.get(1));
		for (int i = 2; i < n; i++)
		{
			while (up.size() >= 2)
			{
				int m = up.size();
				// Checking if the point turned left or not.
				if (cross(up.get(m - 1), up.get(m - 2), Points.get(i)) > 0)
				{
					int idx = m - 1;
					up.remove(idx);
				}
				else
				{
					break;
				}
			}
			up.add(Points.get(i));
		}
		// Finding the lower hull/parameter.
		down.add(Points.get(n - 1));
		down.add(Points.get(n - 2));
		for (int i = n - 3; i >= 0; i--)
		{
			while (down.size() >= 2)
			{
				int m = down.size();
				// Checking if the point turned left or not.
				if (cross(down.get(m - 1), down.get(m - 2), Points.get(i)) > 0)
				{
					int idx = down.size() - 1;
					down.remove(idx);
				}
				else
				{
					break;
				}
			}
			down.add(Points.get(i));
		}
		// Finding the distinct points in 'up' + 'down'.
		HashSet<ArrayList<Integer>> s = new HashSet<ArrayList<Integer>>();
		ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
		for (ArrayList<Integer> i : up)
		{
			if (s.contains(i) == false)
			{
				ans.add(i);
				s.add(i);
			}
		}
		for (ArrayList<Integer> i : down)
		{
			if (s.contains(i) == false)
			{
				ans.add(i);
				s.add(i);
			}
		}
		Collections.sort(ans, new Comparator<ArrayList<Integer>>() {    
			public int compare(ArrayList<Integer> a, ArrayList<Integer> b) {
				int la = a.size();
				int lb = b.size();
				int i=0,j=0;
				while(i<la && j<lb){
					if(a.get(i) == b.get(j))
					{
						i++;j++;
					}else if(a.get(i) > b.get(j)){
						return 1;
					}else{
						return -1;
					}
				}
				return 0;
				
			}               
		});
		return ans;
	}

}

Python

'''
    Time Complexity: O(N * log(N))
    Space Complexity: O(N)

    Where 'N' is the number of points.
'''

from typing import *

def cross(p, q, r) :  
    ax = r[0] - p[0]
    ay = r[1] - p[1]
    bx = q[0] - p[0]
    by = q[1] - p[1]
    return ax * by - ay * bx


def construct(Points : List[List[int]]) -> List[List[int]] : 
    
    Points.sort()
    n = len(Points)

    up = []
    down = []
    # Finding the upper hull/parameter.
    up.append(Points[0])
    up.append(Points[1])

    for i in range(2, n) : 

        while (len(up) >= 2) : 
    
            m = len(up)
            # Checking if the poturned left or not.
            if (cross(up[m - 1], up[m - 2], Points[i]) > 0) :
                up.pop()
            else :
                break
            
        up.append(Points[i])
    
    # Finding the lower hull/parameter.
    down.append(Points[n - 1])
    down.append(Points[n - 2])

    for i in range(n - 3, -1, -1) :

        while (len(down) >= 2) : 
    
            m = len(down)
            # Checking if the poturned left or not.
            if (cross(down[m - 1], down[m - 2], Points[i]) > 0) :
                down.pop()
            else : 
                break
            
        down.append(Points[i])
    
    # Finding the distinct points in 'up' + 'down'.
    s = set()
    ans = []
    for i in up : 
        if (tuple(i) not in s) :
            ans.append(i)
            s.add(tuple(i))
        
    for i in down :
        if (tuple(i) not in s) :
            ans.append(i)
            s.add(tuple(i))

    return ans

C++

/*
    Time Complexity: O(N * log(N))
    Space Complexity: O(N)

    Where 'N' is the number of points.
*/

long long cross(vector<int> p, vector<int> q, vector<int> r)
{
    long long ax = r[0] - p[0];
    long long ay = r[1] - p[1];
    long long bx = q[0] - p[0];
    long long by = q[1] - p[1];
    return ax * by - ay * bx;
}


vector<vector<int>> construct(vector<vector<int>> Points)
{
    sort(Points.begin(), Points.end());
    int n = Points.size();

    vector<vector<int>> up, down;
    // Finding the upper hull/parameter.
    up.push_back(Points[0]);
    up.push_back(Points[1]);
    for (int i = 2; i < n; i++)
    {
        while (up.size() >= 2)
        {
            int m = up.size();
            // Checking if the point turned left or not.
            if (cross(up[m - 1], up[m - 2], Points[i]) > 0)
            {
                up.pop_back();
            }
            else
            {
                break;
            }
        }
        up.push_back(Points[i]);
    }
    // Finding the lower hull/parameter.
    down.push_back(Points[n - 1]);
    down.push_back(Points[n - 2]);
    for (int i = n - 3; i >= 0; i--)
    {
        while (down.size() >= 2)
        {
            int m = down.size();
            // Checking if the point turned left or not.
            if (cross(down[m - 1], down[m - 2], Points[i]) > 0)
            {
                down.pop_back();
            }
            else
            {
                break;
            }
        }
        down.push_back(Points[i]);
    }
    // Finding the distinct points in 'up' + 'down'.
    set<vector<int>> s;
    vector<vector<int>> ans;
    for (auto& i : up)
    {
        if (s.find(i) == s.end())
        {
            ans.push_back(i);
            s.insert(i);
        }
    }
    for (auto& i : down)
    {
        if (s.find(i) == s.end())
        {
            ans.push_back(i);
            s.insert(i);
        }
    }
    return ans;
}

java

python

beginners

programming

493 views

0 replies

7 upvotes

Console