Encuentre el valor mínimo de y para los valores de x dados en las consultas Q de todo el conjunto de líneas dado

Dada una array bidimensional arr[][] que consta de pendiente(m) e intercepto(c) para una gran cantidad de líneas de la forma y = mx + c y consultas Q tales que cada consulta contiene un valor x . La tarea es encontrar el valor mínimo de y para los valores de x dados de todos los conjuntos de líneas dados.

Ejemplos:  

Entrada: arr[][] ={ {1, 1}, {0, 0}, {-3, 3} }, Q = {-2, 2, 0} 
Salida: -1, -3, 0 
Explicación: 
Para la consulta x = -2, los valores de y de las ecuaciones son -1, 0, 9. Entonces, el valor mínimo es -1 
De manera similar, para x = 2, los valores de y son 3, 0, -3. Entonces, el valor mínimo es -3 
y para x = 0, los valores de y = 1, 0, 3, por lo que el valor mínimo es 0.

Entrada: arr[][] ={ {5, 6}, {3, 2}, {7, 3} }, Q = { 1, 2, 30 } 
Salida: 5, 8, 92  

Enfoque ingenuo: El enfoque ingenuo consiste en sustituir los valores de x en cada línea y calcular el mínimo de todas las líneas. Para cada consulta, llevará un tiempo O(N), por lo que la complejidad de la solución se convierte en O(Q * N), donde N es el número de líneas y Q es el número de consultas.

Enfoque eficiente: la idea es usar el truco   del casco convexo :

• Del conjunto de líneas dado, las líneas que no tienen significado (para cualquier valor de x, nunca dan el valor mínimo de y) se pueden encontrar y eliminar, reduciendo así el conjunto.
• Ahora, si se pueden encontrar los rangos (l, r) donde cada línea da el valor mínimo, entonces cada consulta se puede responder mediante la búsqueda binaria.
• Por lo tanto, se crea un vector ordenado de líneas con orden decreciente de pendientes y las líneas se insertan en orden decreciente de pendientes.

A continuación se muestra la implementación del enfoque anterior:  

// 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 code
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 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 implementation of the above approach
import 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 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
    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

-1
-3
0

Complejidad de tiempo: O (max (N * logN, Q * logN)), ya que estamos usando una función de ordenación incorporada para ordenar una array de tamaño N que costará O (N * logN) y estamos usando un bucle para atravesar Q veces y en cada recorrido, estamos llamando al método minQuery que cuesta tiempo de registro. Donde N es el número de líneas y Q es el número de consultas.
Espacio Auxiliar: O(N), ya que estamos usando espacio extra.