Algoritmo que calcula el coste mínimo de un aqueducto en base a los parámetros del archivo de entrada.
Uso:
$ ./aqueducte.py <fitxer entrada>
Para calcular el menor coste del aqueducto, teniendo en cuenta 2 casos:
- Todos los puntos tienen pilares.
- Sólo los puntos de los extremos tienen pilares.
Primero, tras obtener los primeros parámetros y las posiciones x e y de los puntos, comprobamos que los puntos de los pilares de cada arco estén por debajo del centro del semcírculo que forma el arco (que tiene un coste O(n)), si no interfieren, entonces procedemos a calcular el coste, se puede hacer los sumatorios por separado, pero para optimizar, podemos usar un mismo bucle de coste O(n) para calcular 3 cosas:
- Comprobación de puntos válidos por debajo de los arcos
- Sumatorio de alturas de columnas
- Sumatorio de distancias al cuadrado de puntes
Ahora, tenemos que comprobar que todos los puntos del terreno no interfieran con el arco. Los puntos que estén por debajo del centro del arco, está claro que no interfieren, pero los puntos que hay por encima ya no es tan sencillo. Para ésto, hemos pensado hacerlo mediante trigonometría, siguiendo el Teorema de Tales, el ángulo que forma un triángulo inscrito en una circunferencia, con dos vértices alineados con el diámetro, con el tercer vértice en cualquier parte de la circunferencia, éste formará un ángulo rectángulo con los otros vértices, visto de otra manera, cualquier triángulo rectángulo inscrito en una circunferencia tendrá un lado que pasará por el centro de la circunferencia. Ya que como hay que calcular el angulo de cada punto del terreno, el coste será de O(n).
- ángulo < 90º = interfiere, está por encima del arco
- ángulo = 90º = coincide con el arco
- ángulo > 90º = no interfiere, está por debajo del arco
Al final hacemos return del valor mas bajo, ya sea el de múltiples arcos, o el de ún solo arco, en caso de que ambos sean imposibles hacemos return de "impossible"
Por lo que el coste total sería de O(n) + O(n) = O(n)
Coste Teórico Iterativo: O(n)
input:
linea ← string
n_points ← Número de puntos de terreno
h_max ← Altura máxima del aqueducto (A la que los semiírculos son tangentes)
alpha ← alpha
beta ← beta
pos_x ←
pos_y ←
output:
positive integrer / string
for i ← lenght(n_points) coste O(n)
if i < n_points -1
radio ← pos_x[ i + 1 ] - pos_x[ i ]
center ← h_max - radio
if center < pos_y[i] OR center < pos_y[i+1] # Comprobación de que los puntos esten por debajo de los arcos
return "Impossible"
distancia ← pos_x[ i + 1] - pos_x[ i ] # Cálculo de costes de distancias
distancia ← distancia^2
columnas ← columnas + (h_max - pos_y[ i ] ) # Cálculo de costes de alturas
result ← (beta * distancia) + (alhpa * columnas) # Cálculo de los costes totales
return result
for i ← lenght(n_points - 1) coste O(n)
if center < pos_y[ i ] # Si los puntos del terreno están por encima del centro del arco
angulo ← función calculate_angle() coste O(1) # Hay que calcular el angulo que hacen para saber si se solapan
if angulo < 90
return "Impossible" # El terreno interfiere con el aqueducto
columans ← h_max - pos_y [ 0 ] # Cálculo de costes de alturas
columnas ← columnas + h_max - pos_y [ n_points - 1 ]
distancia ← distancia + (( pos_x [ n_points - 1 ] - pos_x [ 0 ] ) ^ 2 ) # Cálculo de costes de distancias
result ← ( columnas * alpha ) + ( distancia * beta ) # Cálculo de los costes totales
return result
Coste total sería de O(n) + (O(n) * O(1)) = O(n)
Coste Práctico Iterativo: O(n)
Uso:
$ ./aqueducte_recursive.py <fitxer entrada>
Para calcular el menor coste del aqueducto, teniendo en cuenta 2 casos:
- Todos los puntos tienen pilares.
- Sólo los puntos de los extremos tienen pilares.
Primero, tras obtener los primeros parámetros y las posiciones x e y de los puntos, comprobamos, de la misma manera que en el iterativo, que los puntos de los pilares de cada arco estén por debajo del centro del semcírculo que forma el arco (que tiene un coste O(n)), si no interfieren, entonces procedemos a calcular el coste usando una llamada recursiva de coste O(n).
Posteriormente, comprobamos que todos los puntos del terreno estén por debajo de un único arco que va desde el primer punto hasta el último (al hacerlo mediante un bucle tiene un coste de O(n)), lo hacemos de la misma manera que en el algoritmo Iterativo, mediante el Teorema de Tales, si todos los puntos están por debajo, entonces procedemos a hacer el cálculo de los costes.
Al final hacemos return del valor mas bajo, ya sea el de múltiples arcos, o el de ún solo arco, en caso de que ambos sean imposibles hacemos return de "impossible"
Por lo que el coste total sería de O(n) + O(n) + O(n) = O(n)
Coste Teórico Recursivo: O(n)
input:
linea ← string
n_points ← numPuntos
h_max ← Altura
alpha ← alpha
beta ← beta
pos_x ← array_X
pos_y ← array_Y
output:
positive integrer / string
if doesnt_overlap_multiple(pos_x[poss_arr], pos_y[poss_arr] coste O(1) # Si los puntos están por debajo de los arcos
if poss_arr < len( pos_x ) - 1
columnas ← (h_max - pos_y[ poss_arr ]) # Cálculo de costes de alturas
total ← alpha * columnas
distancia ← pox_x [ poss_arr - 1] - pox_x[ poss_arr ] # Cálculo de costes de distancias
total ← total + beta * distancia
total ← total + recursive(poss_arr +1 ) coste O(n) # Cálculo de los costes totales recursivamente
else:
columnas ← (h_max - pos_y[ len( pos_x ) - 1]) coste O(1) # Caso simple, coste de la última altura, final
result ← alpha * columnas
return result
return Impossible
if doesnt_overlap_one_arch() coste O(n) # Si los puntos están por debajo del arco
columnas ← (h_max - pos_y[ 0 ]) # Cálculo de costes de alturas
columnas ← (h_max - pos_y[ n_points - 1])
columnas ← alpha * columnas
distancias ← distancias + ((pos_x[n_points - 1] - pos_x[ 0 ]) ^ 2) # Cálculo de costes de distancias
distancias ← beta * distancias
result ← columnas + distancias # Cálculo de costes totales
return result
return Imposible
Coste total sería de (O(1) * O(n)) + (O(1) * O(1)) + O(n) = O(n)
Coste Práctico Recursivo: O(n)
Robert Dragos Trif
Enrique Alejo Subías Melgar