Find the maximum value of Y for a given X from given set of lines

0 0 10 minutes read

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 code
int 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 approach
class 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 code
lines = [ Line(1, 1), Line(0, 0), Line(-3, 3)]
 
Q = [ -2, 2, 1];
n = 3
q = 3;
cht = Convex_HULL_Trick();
 
# Sort the lines
lines.sort(reverse = True)
 
# Add the lines
for i in range(n):
    cht.add(lines[i]);
 
# For each query in Q
for i in range(q): 
    x = Q[i];
    print(cht.maxQuery(x));
  
# This code is contributed by phasing17.

C#

// C# implementation of
// the above approach
 
using 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 approach
 
class 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 code
let 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 approach
 
import 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 zambiatek!