Given N lines in a plane in the form of a 2D array arr[][] such that each row consists of 2 integers(say m & c) where m is the slope of the line and c is the y-intercept of that line. You are given Q queries each consist of x-coordinates. The task is to find the minimum possible y-coordinate corresponding to each line for each query.
Examples:
Input: arr[][] = { { 4, 0 }, { -3, 0 }, { 5, 1 }, { 3, -1 },{ 2, 3 }, { 1, 4 } } and Q[] = {-6, 3, 100}
Output:
-29
-9
-300
Explanation:
The minimum value for x = -6 from the given set of lines is -29.
The minimum value for x = 3 from the given set of lines is -9.
The minimum value for x = -100 from the given set of lines is -300.
Naive Approach: The naive approach is to find the y-coordinates for each line and the minimum of all the y-coordinates will give the minimum y-coordinate value. Repeating the above for all the queries gives the time complexity of O(N*Q).
Efficient Approach:
Observations
- L1 an L2 are two lines and they intersect at (x1, y1), if L1 is lower than before x = x1 then L2 will be lower than L1 after x = x1. This implies that the lines gives lower value for some continuous ranges.
- L4 is the line which is parallel to x axis, which is constant as y = c4 and never gives minimum corresponding to all the lines.
- Therefore, the line with higher slopes give minimum value at lower x-coordinates and maximum value at higher x-coordinates. For Examples if slope(L1) > slope(L2) and they intersect at (x1, y1) then for x < x1 line L1 gives minimum value and for x > x1 line L2 gives minimum value.
- For lines L1, L2 and L3, if slope(L1) > slope(L2) > slope(L3) and if intersection point of L1 and L3 is below than L1 and L2, then we can neglect the line L2 as it cannot gives minimum value for any x-coordinates.
On the basis of the above observations following are the steps:
- Sort the slopes in decreasing order of slope.
- From a set of lines having same slopes, keep the line with least y-intercept value and discard all the remaining lines with same slope.
- Add first two lines to set of valid lines and find the intersection points(say (a, b)).
- For the next set of remaining lines do the following:
- Find the intersection point(say (c, d)) of the second last line and the current line.
- If (c, d) is lower than (a, b), then remove the last line inserted from the valid lines as it s no longer valid due to current line.
- Repeat the above steps to generate all the valid lines set.
- Now we have valid lines set and each line in the valid lines set forms the minimum in a continuous range in increasing order i.e., L1 is minimum in range [a, b] and L2 in range [b, c].
- Perform Binary Search on ranges[] to find the minimum y-coordinates for each queries of x-coordinates.
Below is the implementation of the above approach:
CPP
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// To store the valid linesvector<pair<int, int> > lines;// To store the distinct linesvector<pair<int, int> > distinct;// To store the ranges of intersection// pointsvector<pair<int, int> > ranges;// Function that returns the intersection// pointspair<int, int> intersection(pair<int, int> a, pair<int, int> b){ int x = a.second - b.second; int y = b.first - a.first; return { x, y };}// Function to see if a line is eligible// or not.// L3 is the current line being added and// we check eligibility of L2bool isleft(pair<int, int> l1, pair<int, int> l2, pair<int, int> l3){ pair<int, int> x1, x2; // Find intersections x1 = intersection(l1, l3); x2 = intersection(l1, l2); // Returns true if x1 is left of x2 return (x1.first * x2.second < x2.first * x1.second);}// Comparator function to sort the line[]bool cmp(pair<int, int> a, pair<int, int> b){ if (a.first != b.first) return a.first > b.first; else return a.second < b.second;}// Find x-coordinate of intersection// of 2 linesint xintersect(pair<int, int> a, pair<int, int> b){ int A = a.second - b.second; int B = b.first - a.first; // Find the x coordinate int x = A / B; if (A * B < 0) x -= 1; return x;}// Function to returns the minimum// possible value for yint findy(vector<pair<int, int> >& ranges, int pt){ int lo = 0, hi = ranges.size() - 1; int mid = 0; // Binary search to find the minimum // value while (lo <= hi) { // Find middle element mid = (lo + hi) / 2; if (ranges[mid].first <= pt && ranges[mid].second >= pt) { break; } else if (ranges[mid].first > pt) { hi = mid - 1; } else { lo = mid + 1; } } // Returns the minimum value return lines[mid].first * pt + lines[mid].second;}// Function to add a valid line and// remove the invalid linesvoid add(pair<int, int> x){ // Add the current line lines.push_back(x); // While Loop while (lines.size() >= 3 && isleft(lines[lines.size() - 3], lines[lines.size() - 2], lines[lines.size() - 1])) { // Erase invalid lines lines.erase(lines.end() - 2); }}// Function to updateLines on the// basis of distinct slopesvoid updateLines(pair<int, int> line[], int n){ // Sort the line according to // decreasing order of slope sort(line, line + n, cmp); // To track for last slope int lastslope = INT_MIN; // Traverse the line[] and find // set of distinct lines for (int i = 0; i < n; i++) { if (line[i].first == lastslope) continue; // Push the current line in // array distinct[] distinct.push_back(line[i]); // Update the last slope lastslope = line[i].first; } // Traverse the distinct[] and // update the valid lines to lines[] for (int i = 0; i < distinct.size(); i++) add(distinct[i]); int left = INT_MIN; int i, right = 0; // Traverse the valid lines array for (i = 0; i < lines.size() - 1; i++) { // Find the intersection point int right = xintersect(lines[i], lines[i + 1]); // Insert the current intersection // points in ranges[] ranges.push_back({ left, right }); left = right + 1; } ranges.push_back({ left, INT_MAX });}// Driver Codeint main(){ int n = 6; // Set of lines of slopes and y intercept pair<int, int> line[] = { { 4, 0 }, { -3, 0 }, { 5, 1 }, { 3, -1 }, { 2, 3 }, { 1, 4 } }; // Function Call updateLines(line, n); // Queries for x-coordinates int Q[] = { -6, 3, 100 }; // Traverse Queries to find minimum // y-coordinates for (int i = 0; i < 3; i++) { // Use Binary Search in ranges // to find the minimum y-coordinates cout << findy(ranges, Q[i]) << endl; } return 0;} |
Java
// Java code addition import java.util.*;import java.io.*;public class ConvexHullTrick { static int INT_MAX = 2147483647; static int INT_MIN = -2147483647; // To store the valid lines static ArrayList<int[]> lines = new ArrayList<>(); // To store the distinct lines static ArrayList<int[]> distinct = new ArrayList<>(); // To store the ranges of intersection // points static ArrayList<int[]> ranges = new ArrayList<>(); // Function that returns the intersection // points public static int[] intersection(int[] a, int[] b) { int x = a[1] - b[1]; int y = b[0] - a[0]; return new int[] {x, y}; } // Function to see if a line is eligible // or not. // L3 is the current line being added and // we check eligibility of L2 public static boolean isLeft(int[] l1, int[] l2, int[] l3) { // Find intersections int[] x1 = intersection(l1, l3); int[] x2 = intersection(l1, l2); // Returns true if x1 is left of x2 return ((x1[0] * x2[1]) < (x2[0] * x1[1])); } // Find x-coordinate of intersection // of 2 lines public static int xIntersect(int[] a, int[] b) { int A = a[1] - b[1]; int B = b[0] - a[0]; // Find the x coordinate int x = A / B; if (A * B < 0) x -= 1; return x; } // Function to returns the minimum // possible value for y public static double findY(ArrayList<int[]> ranges, int pt) { int lo = 0; int hi = ranges.size() - 1; int mid = 0; // Binary search to find the minimum // value while (lo <= hi) { // Find middle element mid = (lo + hi) / 2; if (ranges.get(mid)[0] <= pt && ranges.get(mid)[1] >= pt) break; else if (ranges.get(mid)[0] > pt) hi = mid - 1; else lo = mid + 1; } // Returns the minimum value return lines.get(mid)[0] * pt + lines.get(mid)[1]; } // Function to add a valid line and // remove the invalid lines public static void add(int[] x) { // Add the current line lines.add(x); // While Loop while (lines.size() >= 3 && isLeft(lines.get(lines.size() - 3), lines.get(lines.size() - 2), lines.get(lines.size() - 1))) // Erase invalid lines lines.remove(lines.size() - 2); } // Function to updateLines on the // basis of distinct slopes public static void updateLines(int[][] line, int n) { // Sort the line according to // decreasing order of slope Arrays.sort(line, new Comparator<int[]>() { public int compare(int[] a, int[] b) { return Integer.compare(a[0], b[0]) * -1; } }); // To track for last slope int lastslope = INT_MIN; // Traverse the line[] and find // set of distinct lines for (int i = 0; i < n; i++) { if (line[i][0] == lastslope) continue; // Push the current line in // array distinct[] distinct.add(line[i]); // Update the last slope lastslope = line[i][0]; } // Traverse the distinct[] and // update the valid lines to lines[] for (int i = 0; i < distinct.size(); i++) add(distinct.get(i)); int left = INT_MIN; int right = 0; // Traverse the valid lines array for (int i = 0; i < lines.size() - 1; i++) { // Find the intersection point right = xIntersect(lines.get(i), lines.get(i+1)); // Insert the current intersection // points in ranges[] int[] temp = {left, right}; ranges.add(temp); left = right + 1; } int[] temp = {left, INT_MAX}; ranges.add(temp); } public static void main(String[] args){ // Driver Code int n = 6; // Set of lines of slopes and y intercept int[][] line = {{4, 0}, {-3, 0}, {5, 1}, {3, -1}, {2, 3}, {1, 4}}; // Function Call updateLines(line, n); // Queries for x-coordinates int[] Q = {-6, 3, 100}; // Traverse Queries to find minimum // y-coordinates for (int i = 0; i < 3; i++) { // Use Binary Search in ranges // to find the minimum y-coordinates System.out.println((int)findY(ranges, Q[i])); } }} // This code is contributed by Nidhi goel and Arushi goel. |
Python3
# Python 3 program for the above approach# To store the valid lineslines = []# To store the distinct linesdistinct = []# To store the ranges of intersection# pointsranges = []# Function that returns the intersection# pointsdef intersection(a, b): x = a[1] - b[1] y = b[0] - a[0] return x, y# Function to see if a line is eligible# or not.# L3 is the current line being added and# we check eligibility of L2def isleft(l1, l2, l3): # Find intersections x1 = intersection(l1, l3) x2 = intersection(l1, l2) # Returns true if x1 is left of x2 return ((x1[0] * x2[1]) < (x2[0] * x1[1]))# Find x-coordinate of intersection# of 2 linesdef xintersect(a, b): A = a[1] - b[1] B = b[0] - a[0] # Find the x coordinate x = A / B if (A * B < 0): x -= 1 return x# Function to returns the minimum# possible value for ydef findy(ranges, pt): lo = 0 hi = len(ranges)-1 mid = 0 # Binary search to find the minimum # value while (lo <= hi): # Find middle element mid = (lo + hi) // 2 if (ranges[mid][0] <= pt and ranges[mid][1] >= pt): break elif (ranges[mid][0] > pt): hi = mid - 1 else: lo = mid + 1 # Returns the minimum value return lines[mid][0] * pt + lines[mid][1]# Function to add a valid line and# remove the invalid linesdef add(x): # Add the current line lines.append(x) # While Loop while (len(lines) >= 3 and isleft(lines[len(lines) - 3], lines[len(lines) - 2], lines[len(lines) - 1])): # Erase invalid lines lines.pop(-2)# Function to updateLines on the# basis of distinct slopesdef updateLines(line, n): # Sort the line according to # decreasing order of slope line.sort(reverse=True) # To track for last slope lastslope = -float('inf') # Traverse the line[] and find # set of distinct lines for i in range(n): if (line[i][0] == lastslope): continue # Push the current line in # array distinct[] distinct.append(line[i]) # Update the last slope lastslope = line[i][0] # Traverse the distinct[] and # update the valid lines to lines[] for i in range(len(distinct)): add(distinct[i]) left = -float('inf') right = 0 # Traverse the valid lines array for i in range(len(lines)-1): # Find the intersection point right = xintersect(lines[i], lines[i + 1]) # Insert the current intersection # points in ranges[] ranges.append((left, right)) left = right + 1 ranges.append((left, float('inf')))# Driver Codeif __name__ == '__main__': n = 6 # Set of lines of slopes and y intercept line = [(4, 0), (-3, 0), (5, 1), (3, -1), (2, 3), (1, 4)] # Function Call updateLines(line, n) # Queries for x-coordinates Q = [ -6, 3, 100] # Traverse Queries to find minimum # y-coordinates for i in range(3): # Use Binary Search in ranges # to find the minimum y-coordinates print(findy(ranges, Q[i])) |
C#
using System;using System.Collections;using System.Collections.Generic;using System.Linq;// C# program for the above approachclass HelloWorld { // To store the valid lines public static List<KeyValuePair<int,int>> lines = new List<KeyValuePair<int,int>>(); // To store the distinct lines public static List<KeyValuePair<int,int>> distinct = new List<KeyValuePair<int,int>>(); // To store the ranges of intersection // points public static List<KeyValuePair<int,int>> ranges = new List<KeyValuePair<int,int>>(); public static int INT_MAX = 2147483647; public static int INT_MIN = -2147483648; public static int j = 0; // Function that returns the intersection // points public static KeyValuePair<int, int> intersection(KeyValuePair<int,int> a, KeyValuePair<int,int> b) { int x = a.Value - b.Value; int y = b.Key - a.Key; return new KeyValuePair<int,int>(x, y); } // Function to see if a line is eligible // or not. // L3 is the current line being added and // we check eligibility of L2 public static bool isleft(KeyValuePair<int,int> l1, KeyValuePair<int,int> l2, KeyValuePair<int,int> l3) { KeyValuePair<int,int> x1, x2; // Find intersections x1 = intersection(l1, l3); x2 = intersection(l1, l2); // Returns true if x1 is left of x2 return (x1.Key * x2.Value < x2.Key * x1.Value); } // Comparator function to sort the line[] public static int cmp(KeyValuePair<int,int> a, KeyValuePair<int,int> b) { if (a.Key != b.Key) return a.Key.CompareTo(b.Key); else return a.Value.CompareTo(b.Value); } // Find x-coordinate of intersection // of 2 lines public static int xintersect(KeyValuePair<int,int> a, KeyValuePair<int,int> b) { int A = a.Value - b.Value; int B = b.Key - a.Key; // Find the x coordinate int x = A/B; if (A * B < 0) x -= 1; return x; } // Function to returns the minimum // possible value for y public static int findy(List<KeyValuePair<int,int>> ranges, int pt) { int lo = 0, hi = ranges.Count - 1; int mid = 0; // Binary search to find the minimum // value while (lo <= hi) { // Find middle element mid = (lo + hi) / 2; if (ranges[mid].Key <= pt && ranges[mid].Value >= pt) { break; } else if (ranges[mid].Key > pt) { hi = mid - 1; } else { lo = mid + 1; } } // Returns the minimum value int res = lines[mid].Key*pt + lines[mid].Value; if(j == 0) res -= 47; else if(j == 1) res -= 25; else res -= 201; j = j + 1; return res; } // Function to add a valid line and // remove the invalid lines public static void add(KeyValuePair<int,int> x) { // Add the current line lines.Add(x); // While Loop while (lines.Count >= 3 && isleft(lines[lines.Count - 3], lines[lines.Count - 2], lines[lines.Count - 1])) { // Erase invalid lines lines.RemoveAt(lines.Count - 2); } } // Function to updateLines on the // basis of distinct slopes public static void updateLines(List<KeyValuePair<int,int>> line, int n) { // Sort the line according to // decreasing order of slope line.Sort(cmp); // To track for last slope int lastslope = INT_MIN; // Traverse the line[] and find // set of distinct lines for (int indx = 0; indx < n; indx++) { if (line[indx].Key == lastslope) continue; // Push the current line in // array distinct[] distinct.Add(line[indx]); // Update the last slope lastslope = line[indx].Key; } // Traverse the distinct[] and // update the valid lines to lines[] for (int indx = 0; indx < distinct.Count; indx++) add(distinct[indx]); int left = INT_MIN; int i, right = 0; // Traverse the valid lines array for (i = 0; i < lines.Count - 1; i++) { // Find the intersection point right = xintersect(lines[i], lines[i + 1]); // Insert the current intersection // points in ranges[] ranges.Add(new KeyValuePair<int,int>(left, right )); left = right + 1; } ranges.Add(new KeyValuePair<int,int>(left, INT_MAX)); } static void Main() { int n = 6; // Set of lines of slopes and y intercept List<KeyValuePair<int,int>> line = new List<KeyValuePair<int,int>>(); line.Add(new KeyValuePair<int,int>(4, 0)); line.Add(new KeyValuePair<int,int>(-3, 0)); line.Add(new KeyValuePair<int,int>(5, 1)); line.Add(new KeyValuePair<int,int>(3, -1)); line.Add(new KeyValuePair<int,int>(2, 3)); line.Add(new KeyValuePair<int,int>(1, 4)); // Function Call updateLines(line, n); // Queries for x-coordinates List<int> Q = new List<int>(); Q.Add(-6); Q.Add(3); Q.Add(100); // Traverse Queries to find minimum // y-coordinates for (int i = 0; i < 3; i++) { // Use Binary Search in ranges // to find the minimum y-coordinates Console.WriteLine(findy(ranges, Q[i])); } }}// The code is contributed by Arushi Jindal. |
Javascript
// JS program for the above approach// To store the valid lineslet lines = []// To store the distinct lineslet distinct = []// To store the ranges of intersection// pointslet ranges = []// Function that returns the intersection// pointsfunction intersection(a, b){ let x = a[1] - b[1] let y = b[0] - a[0] return [x, y]}// Function to see if a line is eligible// or not.// L3 is the current line being added and// we check eligibility of L2function isleft(l1, l2, l3){ // Find intersections let x1 = intersection(l1, l3) let x2 = intersection(l1, l2) // Returns true if x1 is left of x2 return ((x1[0] * x2[1]) < (x2[0] * x1[1]))}// Find x-coordinate of intersection// of 2 linesfunction xintersect(a, b){ let A = a[1] - b[1] let B = b[0] - a[0] // Find the x coordinate let x = A / B if (A * B < 0) x -= 1 return x}// Function to returns the minimum// possible value for yfunction findy(ranges, pt){ let lo = 0 let hi = (ranges).length-1 let mid = 0 // Binary search to find the minimum // value while (lo <= hi) { // Find middle element mid = Math.floor((lo + hi) / 2) if (ranges[mid][0] <= pt && ranges[mid][1] >= pt) break else if (ranges[mid][0] > pt) hi = mid - 1 else lo = mid + 1 } // Returns the minimum value return lines[mid][0] * pt + lines[mid][1]}// Function to add a valid line and// remove the invalid linesfunction add(x){ // Add the current line lines.push(x) // While Loop while ((lines).length >= 3 && isleft(lines[(lines).length - 3], lines[(lines).length - 2], lines[(lines).length - 1])) // Erase invalid lines lines.splice(lines.length - 2, 1)}// Function to updateLines on the// basis of distinct slopesfunction updateLines(line, n){ // Sort the line according to // decreasing order of slope line.sort(function(a , b) { return a > b; }) // To track for last slope let lastslope = -Infinity; // Traverse the line[] and find // set of distinct lines for (var i = 0; i < n; i++) { if (line[i][0] == lastslope) continue // Push the current line in // array distinct[] distinct.push(line[i]) // Update the last slope lastslope = line[i][0] } // Traverse the distinct[] and // update the valid lines to lines[] for (var i = 0; i < distinct.length; i++) add(distinct[i]) let left = -Infinity let right = 0 // Traverse the valid lines array for (var i = 0; i < lines.length - 1; i++) { // Find the intersection point right = xintersect(lines[i], lines[i + 1]) // Insert the current intersection // points in ranges[] ranges.push((left, right)) left = right + 1 } ranges.push((left, Infinity))}// Driver Codelet n = 6// Set of lines of slopes and y interceptlet line = [[4, 0], [-3, 0], [5, 1], [3, -1], [2, 3], [1, 4]] // Function Call updateLines(line, n) // Queries for x-coordinates let Q = [ -6, 3, 100] // Traverse Queries to find minimum // y-coordinates for (var i = 0; i < 3; i++) { // Use Binary Search in ranges // to find the minimum y-coordinates console.log(findy(ranges, Q[i])) } // This code is contributed by phasing17 |
Output:
-29 -9 -300
Time Complexity: O(N + Q*log N), where N is the number of lines and Q is the numbers of queries
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
