[eside-ghost] Quereis currar en google? Haced algoritmos!

[Juanval]

yeeepa

No se si esto empieza a rozar el punto offtopic, pero... bueno, si se
pasa de raya, me echais la bronca y se pasa a café.

On 1/29/07, Arkaitz <arkaitzj en gmail.com> wrote:
> http://phobeo.com/wordpress/?p=62

Me ha molado el tema, y propongo intentar sacar una solución decente a
los problemas que propone el hombre este.

"Step 1: I have N balloons and a bullet in 3-D space. Write some code
to determine if the bullet is inside of any balloon, if yes, which
balloons. Balloons may overlap. For simplicity, assume all balloons
are spheres of radius 1 and the bullet is a point."

Esta no parece mu complicada. Si no me equivoco, es mirar si la
distancia de cada una hasta el bullet es menor que uno.

[...]
for (int i = 0; i<N;i++)
{
    if(isPointInsideBalloon(px,py,pz, balloons[i].x,balloons[i].y,
balloons[i].z))
        printf("Inside balloon %i\n", i);
}

[...]

bool isPointInsideBalloon(float px, float py, float pz, float bx,
float by, float bz)
{
    return (sqrt( pow(px-bx,2) + pow(py-by,2) + pow(pz-bz,2)) <1.0f)
}

Probablemente se pueda mejorar un poco en cuanto a usar macros,
funciones inline, o cosillas así, pero no se me ocurre cómo mejorar el
algoritmo en sí. En principio yo diría que es de lo mas simple que se
puede hacer.

"Step 2: Now I have K bullets, can you enhance the algorithm so the
complexity is better than O(NK)?"

Aqui es donde viene la jodida. La solución simple y estúpida sería algo en plan:

for(int j = 0; j<K; j++)
    for (int i = 0; i<N;i++)
    {
        if(isPointInsideBalloon(bullets[j].x,bullets[j].y,bullets[j].z,

balloons[i].x,balloons[i].y, balloons[i].z))
            printf("Bullet %i Inside balloon %i\n", j, i);
    }

Pero asi fijo que no bajas del O(NK). No tengo ni idea de complejidad
(maldito Deusto...) pero no parece que sea algo demasiado óptimo.

Lo único que se me ocurre es decir que vas a obviar los bullets dentro
de un balloon que ya ha sido explotado por otro bullet, y metiendo un
break por ahi y cambiando el orden de los "for"s, puedas librarte de
algunas comprobaciones. Pero no se me ocurre nada que mejore
drásticamente el algoritmo.

¿Alguien de por aqui se atreve con alguna optimización que reduzca la
complejidad de ese algoritmo?

taluegoooo