Geometría Computacional

Geometry Algorithm Archive

Convex Hull

Si bien es cierto para resolver el problema del Convex Hull (Cerco convexo) de un conjunto de puntos en el plano me he acostumbrado a usar el algoritmo Convex Hull Monotone Chain el cual tiene complejidad O(nlgn) y cuyo código es bastante sencillo, pero nunca está demás aprender cosas nuevas.

Links:

Wikipedia
Ohio State University
Washington University in St. Louis
Convex Hull Algorithms Applet
Algorithmist
Fudan University
Optimal Output-Sensitive Convex Hull Algorithms in Two and Three Dimensions

Google Code Jam 2009 - Round 1

Bueno participé en la Ronda 1 A pero no clasifique, aprendí que la GCJ apenas tienes un algoritmo que puede resolver el small tienes que aprovecharlo.

No pude participar en la Ronda 1 B debido a que en esos momentos me encontrada dando el examen de la Olimpiada Nacional de Matemática Universitaria.

En la Ronda 1 C afortunadamente logre clasificarme para la Ronda 2, a pesar de que cometí un error tonto en la large de la A y envié otro output para la large de la C.

Sobre los problemas de esta ronda:

All Your Base : Greedy
Center of Mass : Matemática, minimizar una función cuadrática
Bribe the Prisoners : DP

Problemas de la semana

SRM 321 Div 1 Level 1 : Matemática simple, manejar casos
SRM 322 Div 1 Level 1 : Ordenamiento, greedy
SRM 325 Div 1 Level 1 : DP
SRM 326 Div 1 Level 1 : Matemática simple, parseo de cadenas

Problemas de la semana

SRM 316 Div 1 Level 1 : Greedy
SRM 317 Div 1 Level 1 : Recursión
SRM 319 Div 1 Level 1 : Simulación
SRM 447 Div 1 Level 1 : Simulación
SRM 447 Div 1 Level 2 : Minimum vertex cover, bipartite matching, max-flow

Google Code Jam 2009 - Qualification Round

Ya salieron los resultados de la Qualification Round, afortunadamente estuvieron bien mis outputs para los tres Large y terminé ubicado en el puesto 78, bastante bien en comparación con el año pasado, ahora a practicar para la ronda 1.

Sobre como resolvi los problemas:

Alien Language : Adhoc
Watersheds : Union-Find
Welcome to Code Jam : DP

Google Code Jam 2009 - Qualification Round

Hoy empezó la Google Code Jam 2009 con la Qualification Round, logré resolver para los tres problemas sus respectivos Small Input y envie mi output para los Large Input, esto me ubicó en el puesto 89, mañana se verá si me mantengo o si caigo en el ranking :p.