Pintando la ciudad con el CoreTrineo
CoreClaus está elaborando su plan de viaje para repartir los regalos lo más rápido posible. Se ha dado cuenta de que en ciudades grandes, puede repartir regalos más rápidos si cada línea que recorre sobre la ciudad cubre más casas. Y ha trazado un plan con el siguiente formato:
x, y
13, 14
54, 78
...
Indicaciones:
- - Las casas están en un cuadrícula de tamaño desconocido.
- - CoreClaus viajará por los vértices (donde se cruzan las líneas de la cuadrícula) pasando por encima de casas (cada celda de la cuadrícula).
- - Cada vez que el trineo pase por encima de una casa puede repartir un regalo a esa casa.
- - Cada casa puede recibir regalos ilimitados.
- - El plan indica cada vértice que visita yendo en línea recta entre ellos.
¿Puedes contar cuántos regalos va a repartir siguiendo el plan indicado en este archivo?
Ejemplo: Imaginemos que sólo hay dos casas una al lado de otra, es decir la cuadrícula tiene 6 vértices (o esquinas) y 2 celdas (las casas).
(0,1)──(1,1)──(2,1)
│ │ │
│ 1 │ 2 │
│ │ │
(0,0)──(1,0)──(2,0)
Y tenemos el siguiente plan:
x, y
0, 0
2, 1
0, 1
- 1. Empieza en las coordenadas (0,0).
- 2. Al moverse a la coordenada (2,1) pasaría por ambas casas.
- 3. Al moverse a la coordenada (0,1) no pasaría por ninguna casa pues viaja por el borde, y realmente no llega a pasar por encima de ninguna casa.
La respuesta de este ejemplo sería 2
