Given a set of lines represented by a 2-dimensional array arr consisting of slope(m) and intercept(c) respectively and Q queries such that each query contains a value x. The task is to find the maximum value of y for each value of x from all the given a set of lines.
The given lines are represented by the equation y = m*x + c.
Examples:
Input: arr[][2] ={ {1, 1}, {0, 0}, {-3, 3} }, Q = {-2, 2, 1} Output: 9, 3, 2 For query x = -2, y values from the equations are -1, 0, 9. So the maximum value is 9 Similarly, for x = 2, y values are 3, 0, -3. So the maximum value is 3 And for x = 1, values of y = 2, 0, 0. So the maximum value is 2. Input: arr[][] ={ {5, 6}, {3, 2}, {7, 3} }, Q = { 1, 2, 30 } Output: 10, 17, 213
Naive Approach: The naive approach is to substitute the values of x in every line and compute the maximum 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 maximal 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 maximum 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:
CPP
// 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 aren't 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 maximum value // of y for the given x coordinate int maxQuery(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, 1 }; 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.maxQuery(x) << endl; } return 0;} |
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 maximum value # of y for the given x coordinate def maxQuery(self, x): # if there is no lines if (len(self.l) == 0): return 999999999; 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, 1];n = 3q = 3;cht = Convex_HULL_Trick();# Sort the lineslines.sort(reverse = True)# 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.maxQuery(x)); # This code is contributed by phasing17. |
C#
// C# implementation of// the above approachusing System;using System.Collections.Generic;class Line : IComparable<Line> { public int m, c; public Line(int m1, int c1) { m = m1; c = c1; } // Sort the line in decreasing // order of their slopes public int CompareTo(Line l) { // If slopes aren't 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 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 List<Line> l; public Convex_HULL_Trick() { 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--; } // 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 maximum value // of y for the given x coordinate public int maxQuery(int x) { // if there is no lines if (l.Count == 0) return Int32.MaxValue; int low = 0, high = (int)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 { public static void Main(string[] args) { Line[] lines = { new Line(1, 1), new Line(0, 0), new Line(-3, 3) }; int[] Q = { -2, 2, 1 }; 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.maxQuery(x)); } }}// This code is contributed by phasing17 |
Javascript
// JS 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 compare (l) { // If slopes aren't 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 = new Array(); } // 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--; } while ((this.l).length > n) (this.l).pop(); while ((this.l).length < n) (this.l).push(new Line()); // 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 maximum value // of y for the given x coordinate maxQuery( x) { // if there is no lines if ((this.l).length == 0) return 999999999; 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, 1 ];let n = 3, q = 3;let cht = new Convex_HULL_Trick(); // Sort the lines lines.sort(function(a, b) { if (a.m == b.m) return a.c < b.c; return a.m < b.c; }) // Add the lines for (var i = 0; i < n; i++) cht.add(lines[i]); // For each query in Q for (var i = 0; i < q; i++) { var x = Q[i]; console.log(cht.maxQuery(x)) }// This code is contributed by phasing17 |
Java
// Java implementation of// the above approachimport java.util.*;class GFG {static class Line implements Comparable<Line> { public int m, c; public Line(int m1, int c1) { m = m1; c = c1; } // Sort the line in decreasing // order of their slopes public int compareTo(Line l) { // If slopes aren't 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 public 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; public Convex_HULL_Trick() { l = new ArrayList<Line>(); } // Add the line to the set of lines public 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--; } // 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.get(ind)).m * x + (l.get(ind)).c; } // Function to Return the maximum value // of y for the given x coordinate public int maxQuery(int x) { // if there is no lines if (l.size() == 0) 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); }}; public static void main(String[] args) { Line[] lines = { new Line(1, 1), new Line(0, 0), new Line(-3, 3) }; int[] Q = { -2, 2, 1 }; 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.maxQuery(x)); } }}// This code is contributed by phasing17 |
Output:
9 3 2
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!