Find minimum value of y for the given x values in Q queries from all the given set of lines | C ++ implementation of the above approach ; Sort the line in decreasing order of their slopes ; If slopes arent equal ; If the slopes are equal ; 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 ; To store the lines ; Add the line to the set of lines ; To check if after adding the new line whether old lines are losing significance or not ; Add the present line ; Function to return the y coordinate of the specified line for the given coordinate ; Function to Return the minimum value of y for the given x coordinate ; if there is no lines ; Binary search ; Driver code ; Sort the lines ; Add the lines ; For each query in Q
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Line { int m , c ; public : bool operator< ( Line l ) { if ( m != l . m ) return m > l . m ; else return c > l . c ; } 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 { vector < Line > l ; void add ( Line newLine ) { int n = l . size ( ) ; while ( n >= 2 && newLine . check ( l [ n - 2 ] , l [ n - 1 ] , newLine ) ) { n -- ; } l . resize ( n ) ; l = new Line [ n ] ; l . push_back ( newLine ) ; } int value ( int in , int x ) { return l [ in ] . m * x + l [ in ] . c ; } int minQuery ( int x ) { if ( l . empty ( ) ) return INT_MAX ; int low = 0 , high = ( int ) l . size ( ) - 2 ; 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 ) ; } } ; int main ( ) { Line lines [ ] = { { 1 , 1 } , { 0 , 0 } , { -3 , 3 } } ; int Q [ ] = { -2 , 2 , 0 } ; int n = 3 , q = 3 ; Convex_HULL_Trick cht ; sort ( lines , lines + n ) ; for ( int i = 0 ; i < n ; i ++ ) cht . add ( lines [ i ] ) ; for ( int i = 0 ; i < q ; i ++ ) { int x = Q [ i ] ; cout << cht . minQuery ( x ) << endl ; } return 0 ; }