Dado un conjunto de líneas representadas por una array bidimensional arr que consiste en la pendiente (m) y el intercepto (c) respectivamente y Q consultas tales que cada consulta contiene un valor x . La tarea es encontrar el valor máximo de y para cada valor de x de todo el conjunto de líneas dado.
Las rectas dadas están representadas por la ecuación y = m*x + c .
Ejemplos:
Entrada: arr[][2] ={ {1, 1}, {0, 0}, {-3, 3} }, Q = {-2, 2, 1}
Salida: 9, 3, 2
Para consulta x = -2, los valores de y de las ecuaciones son -1, 0, 9. Entonces, el valor máximo es 9
De manera similar, para x = 2, los valores de y son 3, 0, -3. Entonces el valor máximo es 3
Y para x = 1, los valores de y = 2, 0, 0. Entonces el valor máximo es 2.Entrada: arr[][] ={ {5, 6}, {3, 2}, {7, 3} }, Q = { 1, 2, 30 }
Salida: 10, 17, 213
Enfoque ingenuo: El enfoque ingenuo consiste en sustituir los valores de x en cada línea y calcular el máximo de todas las líneas. Para cada consulta, tomará tiempo O (N) y, por lo tanto, 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áximo 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áximo, entonces cada consulta se puede responder usando 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 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;
}
9 3 2
Publicación traducida automáticamente
Artículo escrito por muskan_garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA