2922 - Euclid

[dovier]

http://coj.uci.cu/24h/problem.xhtml?abb=2922

[isaac]

Ese ejercicio se puede hacer basándose en las propiedades del producto cruz entre dos vectores y la suma de vectores además de una muy básica búsqueda binaria. Como información para los que no conocen del tema, el producto cruz entre dos vectores representa el área del paralelogramo del cual son lados consecutivos. La suma de vectores tiene que ver también con el paralelogramo pero esta vez dicha suma nos da el cuarto punto del paralelogramo formado por el origen de coordenadas y los puntos que representan ambos vectores. Luego cuando tenga un poco más de tiempo escribo algo más detallado.

[isaac]

Si tenemos dos vectores v1 y v2, donde v1 = AC y v2 = AB, entonces podemos hacer la siguiente comprobacion:

Mientras | v1 x v2 | < 2 * area_del_triangulo:
v1 = v1 + v1

Luego, hacemos una busqueda binaria cambiando longitud de v1 en dependencia del producto cruz con v2. En este caso, los vectores son representados como puntos. v1 es el vector que va desde el punto A al punto C y v2 el que va de A a B. El producto cruz nos va a dar el area del paralelogramo cuyos lados consecutivos son v1 y v2 respectivamente. OJO: esta area puede ser negativa, asi que se toma el valor absoluto. Para hallar el punto medio de un segmento delimitado por dos puntos A = (A.x, A.y) y B = (B.x, B.y) , seria ((A.x + B.x) / 2, (A.y + B.y) / 2). Quien nos va a evaluar la busqueda binaria va a ser precisamente el producto cruz.

Sugerencia: Si toman los puntos A, B y C y les restan a cada uno las coordenadas de A, van a tener el mismo sistema pero con A como origen. Asi se harian mas faciles las operaciones y al final, se le sumarian de nuevo las coordenadas de A que habria que guardarlas en una variable auxiliar.

Un pequeño ejemplo de la busqueda planteada es este:

Code: Select all

	    
	    mid = (lo + hi) / 2.0;

            double val = area(a, b, mid) * 2.0;

            if(val > area_tr)
                hi = mid;
            else
                lo = mid;
                

Ahi lo, hi y mid son datos de una struct que hice donde guardaba la coordenada x e y de un punto. Por supuesto, las operaciones que se ven ahi, estan definidas en la estructura. La funcion area() recibe tres puntos y devuelve el area del triangulo correspondiente. Como lo que se necesita es el area del paralelogramo, simplemente multiplicamos el resultado por 2. Vease que esta busqueda binaria es con valores reales, por tanto hay que ponerle una cierta tolerancia a la hora de las comparaciones, o en mi caso particular, meti la busqueda en un for y lo repeti 100 veces. Creo que es mas que suficiente para un resultado optimo.

[yurisdan]

Qué es una búsqueda binaria???....Gracias

[isaac]

Una busqueda binaria es una tecnica que se utiliza cuando quieres buscar un valor en un conjunto ordenado de elementos. Se utiliza por su eficiencia a la hora de arrojar un resultado. Te explico, imagina que tienes un conjunto de elementos ordenados: { 1, 1, 2, 4, 5, 6, 7, 7, 8, 9} y quieres buscar el 8. Si haces una busqueda lineal, vas a tener que recorrer casi todo el conjunto. Sin embargo puedes hacer lo siguiente (busqueda binaria)

Tomas dos valores que representan el indice inicial y final donde vas a efectuar la busqueda respectivamente.
ini = 1
fin = 10

El algoritmo se basa en lo siguiente:

Code: Select all

	while( ini <= fin) {
		// Indice que esta en el medio del intervalo
		mid = (ini + fin) / 2;
		
		// compruebas si el elemento en esa posicion es el que buscas
		if( conjunto [ mid ] == 8 )
			return mid;
		
		// verificas si el elemento que estas buscando esta en la mitad
		// izquierda o derecha del intervalo y reajustas los puntos extremos
		// sobre los cuales te basas para la busqueda.
		if(conjunto [mid] > 8)
			fin = mid - 1;
		else
			ini = mid + 1;
			
	}

Debes notar que si el numero (en este caso) que estas buscando no aparece en la lista, entonces el while va a romperse eventualmente. Si haces la comprobacion a mano vas a ver que el intervalo cada vez se va reduciendo a la mitad, por lo que si tienes N elementos, va a hacer solo log2 N pasos antes de encontrar o no un resultado. En el caso del problema correspondiente, se sabe que una vez que el tamaño del vector v1 (que va de A a C) se reajusta, la respuesta va a estar contenida en el intervalo entre el punto A y el punto C. En ese caso, como trabajamos con numeros reales, a la hora de redefinir los limites de la busqueda hay que tener especial cuidado.