Concurso de Mictlan: TJU Contest #10

Posted Abril 26, 2008

Publico mis soluciones a los problemas del pasado concursito en el sitio de la Universidad Tecnológica de la Mixteca - Mictlan: TJU Contest #10, en el orden en que los resolví. En general me gustó el torneo, los problemas estuvieron variados y bien escogidos. Lástima que al final se cayó el servidor y no pude terminar el problema que me quedó faltando.

  • El primer problema que resolví fue el 2772 - Parallelogram. Consiste en determinar si 4 puntos dados podrían ser las esquinas de un paralelogramo. Utilicé la ecuación canónica LaTeX - ax + by + c = 0 de una recta para resolverlo.
    Este es el código: 2772.cpp
  • Después hice 2189 - The key stations: Hallar los puntos de articulación de un grafo no dirigido. Hay un problema casi idéntico en el sitio de la Universidad de Valladolid. Ya lo había hecho, así que conocía el algoritmo y reciclé código. El algoritmo está en el libro “Introduction to Algorithms” de Thomas Cormen y otros.

    No me gustó el formato de entrada de este problema. Me dio Accepted al segundo intento, por un estúpido Presentation Error.
    Este es el código: 2189.cpp

  • 2028 - Excuses, excuses!. Un problema ad-hoc de strings. Utilicé un mapa para el diccionario y un stringstream para dividir una frase en palabras.
    Otro Presentation error más estúpido todavía me dio otros 20 minutos de penalización.
    El código: 2028.cpp
  • Finalmente resolví 1058 - Lifting the stones. Para mi gusto el mejor problema del set. Se resume así: Dado un polígono simple (es decir, que no se intersecta a sí mismo) que representa una lámina de densidad superficial constante, encontrar las coordenadas del centro de masa de la lámina.

    Resolví este problema aplicando el Teorema de Green, que relaciona la integral doble de una región con la integral de línea de la curva que la encierra. En otras palabras:

    LaTeX - \int_{C} \vec{F} \cdot \, d\vec{r} = \iint_{R} \left( \frac{\partial Q}{\partial x} - \frac{\partial P}{\partial y} \right) \, dA donde LaTeX - \vec{F} es un campo vectorial de la forma LaTeX - \vec{F} = < P(x,y) , Q(x, y) > .

    Ahora bien, la coordenada LaTeX - X centro de masa de una lámina plana está dada por:

    LaTeX - \bar{C}_{x} = \frac{ \iint_{R} \rho \, x \, dA }{M} donde LaTeX - \rho es la función de densidad (en este problema una constante que podemos considerar LaTeX - \rho = 1 ) y LaTeX - M es la masa neta de la lámina.

    Similarmente, la coordenada LaTeX - Y es:
    LaTeX - \bar{C}_{y} = \frac{ \iint_{R} \rho \, y \, dA }{M} .

    La parte crítica del problema es ver que las integrales dobles que aparecen en los denominadores se pueden expresar como una integral de línea, y esta se puede evaluar conociendo los puntos del polígono porque un polígono simple es una curva cerrada suave a trozos donde cada trozo es una recta.

    Sea LaTeX - \vec{F} un campo vectorial con la forma LaTeX - \vec{F} = < P(x,y) , Q(x,y) > = < 0, \frac{x^2}{2} >

    Derivando parcialmente obtenemos que:
    LaTeX - \frac{\partial Q}{\partial x} - \frac{\partial P}{\partial y} = x

    Que es justamente la función que queremos integrar.

    Aplicando el Teorema de Green llegamos a que:
    LaTeX - \iint_{R} x \, dA = \iint_{R} \left( \frac{\partial Q}{\partial x} - \frac{\partial P}{\partial y} \right) \, dA

    LaTeX - = \int_{C} \vec{F} \cdot \, d\vec{r} = \int_{C} P \, dx + Q \, dy

    pero como el polígono es una curva suave a trozos podemos expresar esta última integral como la suma de una integral por tramo:

    LaTeX - = \int_{C_1} P \, dx + Q \, dy +\, \cdots \, + \int_{C_n} P \, dx + Q \, dy

    LaTeX - = \sum_{i=1}^{n} \int_{C_i} P \, dx + Q \, dy

    Ahora sólo hace falta parametrizar la curva LaTeX - C_{i} para evaluar esta integral de línea.
    Dado que LaTeX - C_i es una recta que va de los puntos LaTeX - (x_{i}, y_{i}) a LaTeX - (x_{i+1}, y_{i+1}) la parametrizamos con la función vectorial LaTeX - \vec{r} = < t , \, m (x - x_i) + y_i > donde el parámetro LaTeX - x_{i} \leq t \leq x_{i+1} La primera coordenada de esta función es lo que hemos llamado LaTeX - x y la segunda es lo que hemos llamado LaTeX - y , y LaTeX - m es la pendiente de la recta LaTeX - C_i . Derivando estás funciones vemos que LaTeX - dx = dt y LaTeX - dy = m \, dt .

    Entonces nuestra integral de línea en cuestión queda

    LaTeX - \int_{C_i} P \, dx + Q \, dy = \int_{x_i}^{x_{i+1}} 0 \, dt + \frac{x^2}{2} m \, dt

    LaTeX - = \int_{x_i}^{x_{i+1}} \frac{x^2}{2} m \, dt

    Una integral fácil de evaluar cuyo resultado es

    LaTeX - = \frac{1}{6} m\, \left( x_{i+1}^3 - x_{i}^3 \right)

    Teniendo en cuenta que LaTeX - m = \frac{y_{i+1} - y_i}{x_{i+1} - x_{i}} y aplicando un poco de álgebra, vamos a llegar por fin a la solución:

    LaTeX - \bar{C}_{x} = \frac{ \iint_{R} x \, dA }{M} = \frac{1}{6M} \sum_{i=1}^{n} (y_{i+1} - y_{i}) (x_{i+1}^2 + x_{i+1} x_{i} + x_{i}^2)

    Para la coordenada LaTeX - Y es un proceso casi idéntico, pero me da mucha pereza escribirlo acá.
    La respuesta es:

    LaTeX - \bar{C}_{y} = \frac{ \iint_{R} y \, dA }{M} = \frac{1}{6M} \sum_{i=1}^{n} (x_{i} - x_{i+1}) (y_{i+1}^2 + y_{i+1} y_{i} + y_{i}^2)

    Sólo faltan dos detalles para poder codificar una solución aceptada por el juez: Para efectos de este problema, la masa es directamente proporcional al área del polígono. El área se encuentra con el algoritmo explicado en el libro Programming Challenges de Miguel Revilla. El otro detalle es que el teorema de Green nos exige que la curva cerrada esté orientada en sentido antihorario, así que si el polígono original está en sentido horario hay que reversarlo antes de correrle este algoritmo.

    Tengo que decir que gran parte de esto salió de la cabezota de Arcila.

    De cualquier modo, aquí está el código: 1058.cpp

    Ahh por cierto, pudieron ahorrarse el trabajo de leer toda esta vomitadera matemática leyendo esto (Tal vez debí poner este anuncio arriba).

Nota del autor: Buah, acabo de leer todo lo anterior y me parece sumamente aburrido. Necesito bailar un rato.

3 Comments so far

  1. Federico Builes on Abril 27th, 2008

    Espera, ¿me estás diciendo entonces que todo este calculo de varias variables sí sirve para algo?!

    Mis ilusiones…rotas.

  2. Andrés on Abril 27th, 2008

    Todo lo que sirva para resolver problemas en torneos es de gran utilidad en la vida.

  3. jpemberthy on Mayo 16th, 2008

    jaja veo que estas progresando mucho, felicitaciones :P

Leave a reply