Mientras Haskell Curry respuesta da una solución matemática al problema, pensé que me iba a ofrecer un servicio más programador orientado a la solución de los mismos; en particular, vale la pena señalar que el problema puede ser resuelto sin el cálculo de una raíz cuadrada.
En primer lugar, como ya se ha señalado, su pregunta es equivalente a considerar la función de $f(x) = y_1(x)-y_2(x) =Ax^2+Bx+C$ ( $A=a-d$ , etc.) y prueba si $f(x) \gt 0$ durante un intervalo de $x\in [x_1, x_2]$; voy a utilizar esta formulación del problema.
A continuación, considere el vértice de la parábola $(x,f(x))$; es decir, el punto de $x_0=-B/2A$ que representa el eje de simetría de la función $f$. ($f$ puede ser escrito como $f(x) = A(x-x_0)^2+M$ para algunas constantes $M$ y este es, de hecho, la génesis de la fórmula cuadrática, pero eso es irrelevante para el problema en la mano). Si $x_0$ no está en el intervalo de $[x_1, x_2]$ (y tenga en cuenta que esto también cubre el caso de degeneración donde $A=0$, es decir, donde no hay ningún vértice), entonces la función de $f$ debe ser estrictamente creciente o estrictamente decreciente en dicho rango; esto significa que sólo podemos ver los signos de $f(x_1)$$f(x_2)$, y estar seguro de que si ambos son positivos, $f$ es positiva en todo el intervalo.
Por otro lado, si $x_0$ está en el intervalo, entonces $f$ toma en un máximo o de un mínimo de allí (dependiendo del signo de $A$), y esto significa que $f(x)$ será estrictamente creciente en uno de los dos intervalos de $[x_1, x_0]$ o $[x_0, x_2]$ y estrictamente decreciente en el otro. Aquí, sólo podemos ver el signo de $f(x)$ en los tres puntos $x=x_0$, $x=x_1$ y $x=x_2$; si cualquiera de ellos es negativo, entonces obviamente $f$ es negativo en algún punto en el intervalo, pero si todos los tres son positivos, a continuación, por el 'bitonicity' de $f$ sabemos que debe ser positiva en la totalidad del intervalo. Esto nos da la siguiente (pseudocódigo) de la función:
bool PositiveOnRange(Quadratic f, float x1, float x2)
{
if (f.evalAt(x1) <= 0) return false; // negative at one end of the range
if (f.evalAt(x2) <= 0) return false; // negative at the other end
if ( f.A == 0 ) return true; // not actually quadratic
float x0 = -f.B/(2.0*f.A);
if ( (x0 < x1) || (x0 > x2) ) return true; // vertex not in range
return ( f.evalAt(x0) > 0 ); // sign at vertex
}
Para funciones que no son tan simples como cuadráticas, el enfoque más sencillo podría ser una combinación de subdivisión y la aritmética de intervalos; esencialmente, cuando la evaluación de una función (esto funciona especialmente bien para los polinomios, pero tenga en cuenta que las exponenciales y arbitrario de funciones monótonas son bien comportados por la aritmética de intervalos demasiado), en lugar de evaluar en un punto a evaluar es 'en' un intervalo. Los intervalos pueden ser sumados y multiplicados con reglas simples, y de cualquier forma monotónica $f(x)$ evaluado en un intervalo de $I=[a, b]$ los rendimientos de la (posiblemente mal ordenados) intervalo de $f(\!(I)\!) = [f(a), f(b)]$. Aritmética de intervalos no es necesariamente estricto - para una función arbitraria $f$, si calculamos el $f(\!(I)\!) = J = [J_l, J_r]$, a continuación, esto no necesariamente significa que cada valor de $J_l\lt y\lt J_r$ $f(x)$ algunos $x\in I$ -, pero es conservador, en el sentido de que si $f(\!(I)\!) = J$, entonces para cada a $x\in I$ tenemos $f(x)\in J$.
El uso de aritmética de intervalos, el problema entonces puede ser resuelto con un divide y vencerás algoritmo: inicio con el intervalo de $I=[x_L, x_R]$ desea confirmar $f()\gt 0$. Comenzar por evaluar $f(x_L)$ $f(x_R)$ a asegurarse de que sus extremos son ambos positivos. Suponiendo que pasa, calcular los $f(\!(I)\!)$ y prueba para ver si contiene 0. Si no, entonces usted está hecho; usted sabe que su función debe ser positiva en el intervalo. Si no contener $0$, por otro lado, luego de evaluar $f$ en la mitad de la $x_M = \frac{(x_L+x_R)}{2}$. De nuevo, si esto falla, entonces usted está hecho; si tiene éxito, entonces se debe considerar los dos intervalos de $I_L = [x_L, x_M]$$I_R = [x_M, x_R]$. Usted puede evaluar $f(\!(I_L)\!)$ para ver si contiene 0 (y recurse hacia abajo hasta que falle o, finalmente, empezar a intervalos que son "buenos"), y hacer lo mismo con $f(\!(I_R)\!)$. Esto da el siguiente pseudocódigo (que probablemente deben ser convertidos para el uso explícito de la pila de intervalos en lugar de la recursividad y, por supuesto, necesita un poco de cordura-controles para evitar recursing infinitamente, pero esos son detalles de la programación):
bool PositiveOnRange(Function f, float xL, float xR)
{
// we presume that xL and xR have already been tested and confirmed positive.
Interval testInterval = f.evalOnInterval(Interval(xL, xR));
if ( !(testInterval.Contains(0)) ) return true;
float xM = 0.5*(xL+xR);
if ( f.evalAt(xM) < 0 ) return false;
return (PositiveOnRange(f, xL, xM) && PositiveOnRange(f, xM, xR));
}
