Given a 2-dimensional array arr[][] consisting of slope(m) and intercept(c) for a large number of lines of the form y = mx + c and Q queries such that each query contains a value x. The task is to find the minimum value of y for the given x values from all the given sets of lines.
Examples:
Input: arr[][] ={ {1, 1}, {0, 0}, {-3, 3} }, Q = {-2, 2, 0}
Output: -1, -3, 0
Explanation:
For query x = -2, y values from the equations are -1, 0, 9. So the minimum value is -1
Similarly, for x = 2, y values are 3, 0, -3. So the minimum value is -3
And for x = 0, values of y = 1, 0, 3 so min value is 0.Input: arr[][] ={ {5, 6}, {3, 2}, {7, 3} }, Q = { 1, 2, 30 }
Output: 5, 8, 92
Naive Approach: The naive approach is to substitute the values of x in every line and compute the minimum of all the lines. For each query, it will take O(N) time and so the complexity of the solution becomes O(Q * N) where N is the number of lines and Q is the number of queries.
Efficient approach: The idea is to use convex hull trick:
- From the given set of lines, the lines which carry no significance (for any value of x they never give the minimal value y) can be found and deleted thereby reducing the set.
- Now, if the ranges (l, r) can be found where each line gives the minimum value, then each query can be answered using binary search.
- Therefore, a sorted vector of lines with decreasing order of slopes is created and the lines are inserted in decreasing order of the slopes.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;struct Line { int m, c;public: // Sort the line in decreasing // order of their slopes bool operator<(Line l) { // If slopes arent equal if (m != l.m) return m > l.m; // If the slopes are equal else return c > l.c; } // Checks if line L3 or L1 is better than L2 // Intersection of Line 1 and // Line 2 has x-coordinate (b1-b2)/(m2-m1) // Similarly for Line 1 and // Line 3 has x-coordinate (b1-b3)/(m3-m1) // Cross multiplication will give the below result bool check(Line L1, Line L2, Line L3) { return (L3.c - L1.c) * (L1.m - L2.m) < (L2.c - L1.c) * (L1.m - L3.m); }};struct Convex_HULL_Trick { // To store the lines vector<Line> l; // Add the line to the set of lines void add(Line newLine) { int n = l.size(); // To check if after adding the new line // whether old lines are // losing significance or not while (n >= 2 && newLine.check(l[n - 2], l[n - 1], newLine)) { n--; } l.resize(n); // Add the present line l.push_back(newLine); } // Function to return the y coordinate // of the specified line for the given coordinate int value(int in, int x) { return l[in].m * x + l[in].c; } // Function to Return the minimum value // of y for the given x coordinate int minQuery(int x) { // if there is no lines if (l.empty()) return INT_MAX; int low = 0, high = (int)l.size() - 2; // Binary search while (low <= high) { int mid = (low + high) / 2; if (value(mid, x) > value(mid + 1, x)) low = mid + 1; else high = mid - 1; } return value(low, x); }};// Driver codeint main(){ Line lines[] = { { 1, 1 }, { 0, 0 }, { -3, 3 } }; int Q[] = { -2, 2, 0 }; int n = 3, q = 3; Convex_HULL_Trick cht; // Sort the lines sort(lines, lines + n); // Add the lines for (int i = 0; i < n; i++) cht.add(lines[i]); // For each query in Q for (int i = 0; i < q; i++) { int x = Q[i]; cout << cht.minQuery(x) << endl; } return 0;} |
Java
// Java implementation of the above approachimport java.util.ArrayList;import java.util.Arrays;class GFG{static class Line implements Comparable<Line> { int m, c; public Line(int m, int c) { this.m = m; this.c = c; } // Sort the line in decreasing // order of their slopes @Override public int compareTo(Line l) { // If slopes arent equal if (m != l.m) return l.m - this.m; // If the slopes are equal else return l.c - this.c; } // Checks if line L3 or L1 is better than L2 // Intersection of Line 1 and // Line 2 has x-coordinate (b1-b2)/(m2-m1) // Similarly for Line 1 and // Line 3 has x-coordinate (b1-b3)/(m3-m1) // Cross multiplication will give the below result boolean check(Line L1, Line L2, Line L3) { return (L3.c - L1.c) * (L1.m - L2.m) < (L2.c - L1.c) * (L1.m - L3.m); }}static class Convex_HULL_Trick { // To store the lines ArrayList<Line> l = new ArrayList<>(); // Add the line to the set of lines void add(Line newLine) { int n = l.size(); // To check if after adding the new // line whether old lines are // losing significance or not while (n >= 2 && newLine.check(l.get(n - 2), l.get(n - 1), newLine)) { n--; } // l = new Line[n]; // Add the present line l.add(newLine); } // Function to return the y coordinate // of the specified line for the given // coordinate int value(int in, int x) { return l.get(in).m * x + l.get(in).c; } // Function to Return the minimum value // of y for the given x coordinate int minQuery(int x) { // If there is no lines if (l.isEmpty()) return Integer.MAX_VALUE; int low = 0, high = (int)l.size() - 2; // Binary search while (low <= high) { int mid = (low + high) / 2; if (value(mid, x) > value(mid + 1, x)) low = mid + 1; else high = mid - 1; } return value(low, x); }};// Driver codepublic static void main(String[] args) { Line[] lines = { new Line(1, 1), new Line(0, 0), new Line(-3, 3) }; int Q[] = { -2, 2, 0 }; int n = 3, q = 3; Convex_HULL_Trick cht = new Convex_HULL_Trick(); // Sort the lines Arrays.sort(lines); // Add the lines for(int i = 0; i < n; i++) cht.add(lines[i]); // For each query in Q for(int i = 0; i < q; i++) { int x = Q[i]; System.out.println(cht.minQuery(x)); }}}// This code is contributed by sanjeev2552 |
Python3
# Python3 implementation of the above approachclass Line: def __init__(self, a = 0, b = 0): self.m = a; self.c = b; # Sort the line in decreasing # order of their slopes def __gt__(self, l): # If slopes arent equal if (self.m != l.m): return self.m > l.m; # If the slopes are equal else: return self.c > l.c; # Checks if line L3 or L1 is better than L2 # Intersection of Line 1 and # Line 2 has x-coordinate (b1-b2)/(m2-m1) # Similarly for Line 1 and # Line 3 has x-coordinate (b1-b3)/(m3-m1) # Cross multiplication will give the below result def check(self, L1, L2, L3): return (L3.c - L1.c) * (L1.m - L2.m) < (L2.c - L1.c) * (L1.m - L3.m); class Convex_HULL_Trick : # To store the lines def __init__(self): self.l = []; # Add the line to the set of lines def add(self, newLine): n = len(self.l) # To check if after adding the new line # whether old lines are # losing significance or not while (n >= 2 and newLine.check((self.l)[n - 2], (self.l)[n - 1], newLine)): n -= 1; # Add the present line (self.l).append(newLine); # Function to return the y coordinate # of the specified line for the given coordinate def value(self, ind, x): return (self.l)[ind].m * x + (self.l)[ind].c; # Function to Return the minimum value # of y for the given x coordinate def minQuery(self, x): # if there is no lines if (len(self.l) == 0): return 99999999999; low = 0 high = len(self.l) - 2; # Binary search while (low <= high) : mid = int((low + high) / 2); if (self.value(mid, x) > self.value(mid + 1, x)): low = mid + 1; else: high = mid - 1; return self.value(low, x); # Driver codelines = [ Line(1, 1), Line(0, 0), Line(-3, 3)]Q = [ -2, 2, 0 ];n = 3q = 3;cht = Convex_HULL_Trick();# Sort the lineslines.sort()# Add the linesfor i in range(n): cht.add(lines[i]);# For each query in Qfor i in range(q): x = Q[i]; print(cht.minQuery(x));# This code is contributed by phasing17 |
C#
// C# implementation of the above approachusing System;using System.Collections.Generic;using System.Collections;class Line : IComparable<Line> { public int m, c; public Line(int m, int c) { this.m = m; this.c = c; } // Sort the line in decreasing // order of their slopes public int CompareTo(Line l) { // If slopes arent equal if (m != l.m) return l.m - this.m; // If the slopes are equal else return l.c - this.c; } // Checks if line L3 or L1 is better than L2 // intersection of Line 1 and // Line 2 has x-coordinate (b1-b2)/(m2-m1) // Similarly for Line 1 and // Line 3 has x-coordinate (b1-b3)/(m3-m1) // Cross multiplication will give the below result public bool check(Line L1, Line L2, Line L3) { return (L3.c - L1.c) * (L1.m - L2.m) < (L2.c - L1.c) * (L1.m - L3.m); }};class Convex_HULL_Trick { // To store the lines public List<Line> l = new List<Line>(); // Add the line to the set of lines public void add(Line newLine) { int n = l.Count; // To check if after adding the new // line whether old lines are // losing significance or not while ( n >= 2 && newLine.check(l[n - 2], l[n - 1], newLine)) { n--; } // l = new Line[n]; // Add the present line l.Add(newLine); } // Function to return the y coordinate // of the specified line for the given // coordinate public int value(int ind, int x) { return l[ind].m * x + l[ind].c; } // Function to Return the minimum value // of y for the given x coordinate public int minQuery(int x) { // If there is no lines if (l.Count == 0) return Int32.MaxValue; int low = 0, high = l.Count - 2; // Binary search while (low <= high) { int mid = (low + high) / 2; if (value(mid, x) > value(mid + 1, x)) low = mid + 1; else high = mid - 1; } return value(low, x); }};class GFG { // Driver code public static void Main(string[] args) { Line[] lines = { new Line(1, 1), new Line(0, 0), new Line(-3, 3) }; int[] Q = { -2, 2, 0 }; int n = 3, q = 3; Convex_HULL_Trick cht = new Convex_HULL_Trick(); // Sort the lines Array.Sort(lines); // Add the lines for (int i = 0; i < n; i++) cht.add(lines[i]); // For each query in Q for (int i = 0; i < q; i++) { int x = Q[i]; Console.WriteLine(cht.minQuery(x)); } }}// This code is contributed by phasing17 |
Javascript
// JavaScript implementation of the above approachclass Line { constructor(a = 0, b = 0) { this.m = a; this.c = b; } // Sort the line in decreasing // order of their slopes cmp() { // If slopes arent equal if (this.m != l.m) return this.m > l.m; // If the slopes are equal else return this.c > l.c; } // Checks if line L3 or L1 is better than L2 // Intersection of Line 1 and // Line 2 has x-coordinate (b1-b2)/(m2-m1) // Similarly for Line 1 and // Line 3 has x-coordinate (b1-b3)/(m3-m1) // Cross multiplication will give the below result check(L1, L2, L3) { return (L3.c - L1.c) * (L1.m - L2.m) < (L2.c - L1.c) * (L1.m - L3.m); }};class Convex_HULL_Trick { // To store the lines constructor() { this.l = []; } // Add the line to the set of lines add(newLine) { let n = (this.l).length // To check if after adding the new line // whether old lines are // losing significance or not while (n >= 2 && newLine.check((this.l)[n - 2], (this.l)[n - 1], newLine)) { n--; } // Add the present line (this.l).push(newLine); } // Function to return the y coordinate // of the specified line for the given coordinate value( ind, x) { return (this.l)[ind].m * x + (this.l)[ind].c; } // Function to Return the minimum value // of y for the given x coordinate minQuery( x) { // if there is no lines if ((this.l).length == 0) return 99999999999; let low = 0, high = (this.l).length - 2; // Binary search while (low <= high) { let mid = Math.floor((low + high) / 2); if (this.value(mid, x) > this.value(mid + 1, x)) low = mid + 1; else high = mid - 1; } return this.value(low, x); }};// Driver codelet lines = [ new Line(1, 1), new Line(0, 0), new Line(-3, 3)]let Q = [ -2, 2, 0 ];let n = 3, q = 3;let cht = new Convex_HULL_Trick();// Sort the lineslines.sort()// Add the linesfor (var i = 0; i < n; i++) cht.add(lines[i]);// For each query in Qfor (var i = 0; i < q; i++) { let x = Q[i]; console.log(cht.minQuery(x));}// This code is contributed by phasing17 |
Output
-1 -3 0
Time Complexity: O(max(N*logN, Q*logN)), as we are using an inbuilt sort function to sort an array of size N which will cost O(N*logN) and we are using a loop to traverse Q times and in each traversal, we are calling the method minQuery which costs logN time. Where N is the number of lines and Q is the number of queries.
Auxiliary Space: O(N), as we are using extra space.
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!
