Imagine un grupo de rectángulos dibujados en el plano, cada rectángulo con sus vértices en coordenadas enteras y sus lados paralelos a los ejes:
Los rectángulos dividen el plano en varias regiones disjuntas, de color rojo y azul a continuación:
Su objetivo es encontrar el número de tales regiones que son cuadrados perfectos. En el ejemplo anterior, hay tres:
Tenga en cuenta que el gran cuadrado en el medio no se cuenta, ya que no es una sola región, sino que se compone de varias regiones disjuntas más pequeñas.
Entrada
Puede escribir una función o un programa completo para este desafío.
La entrada será 4n
enteros no negativos que definirán n
rectángulos en el plano. Cada rectángulo está representado por dos vértices opuestos, por ejemplo, 4 9 7 8
representa el rectángulo con vértices opuestos (4, 9)
y (7, 8)
. Tenga en cuenta que este rectángulo también se puede representar como 7 8 4 9
o 4 8 7 9
.
El formato de entrada exacto es flexible (por ejemplo, cadena separada por espacios, cadena separada por comas, matriz única de enteros, lista de tuplas de coordenadas, etc.), pero sea razonable y dé un ejemplo de cómo ejecutar su código en su publicación. No puede reordenar la entrada.
Para simplificar, puede suponer que no se superpondrán dos bordes, esto incluye la superposición en un vértice. En particular, esto implica que no habrá dos rectángulos que se toquen de borde a borde o de esquina a esquina, y los rectángulos tendrán un área distinta de cero.
Salida
Su programa debe imprimir o devolver un número entero único, que es el número de regiones cuadradas.
Tanteo
Este es el código de golf, por lo que gana el código en la menor cantidad de bytes.
Casos de prueba
Entrada:
0 0 5 5
6 8 10 4
14 16 11 13
19 1 18 2
Salida:
4
Esto es simplemente cuatro cuadrados disjuntos:
Entrada:
2 1 3 11
1 10 5 19
6 10 11 3
8 8 15 15
13 13 9 5
15 1 19 7
17 19 19 17
Salida:
3
Este es el caso de prueba de ejemplo al comienzo de la publicación.
Entrada:
0 9 15 12
6 3 18 15
9 6 12 20
13 4 17 8
Salida:
7
Entrada:
5 9 11 10
5 12 11 13
6 8 7 14
9 8 10 14
13 8 14 9
13 10 14 14
Salida:
14
Entrada:
0 99999 100000 0
Salida:
0
Este es solo un gran rectángulo.
Entrada:
0 99999 100000 0
2 1 142857 285714
Salida:
1
Dos grandes rectángulos que se superponen.
Python 2,
480 436 386352 bytesToma una lista de pares de coordenadas a través de STDIN en el formato:
e imprime el resultado en STDOUT.
El programa real, después del reemplazo de la cadena, es:
Explicación
En lugar de jugar con polígonos complejos, este programa trata con segmentos de línea simples. Para cada rectángulo de entrada, agregamos cada uno de sus cuatro bordes a una lista de segmentos colectivos, individualmente. Agregar un segmento a la lista es el siguiente: probamos cada uno de los segmentos existentes para la intersección con el nuevo segmento; Si encontramos una intersección, dividimos ambos segmentos en el punto de intersección y continuamos. Para facilitar las cosas, en realidad mantenemos dos listas de segmentos separadas: una horizontal y una vertical. Como los segmentos no se superponen, los segmentos horizontales solo pueden intersecar segmentos verticales y viceversa. Mejor aún, significa que todas las intersecciones (sin considerar los bordes del mismo rectángulo) son "apropiadas", es decir, no tenemos intersecciones en forma de T, por lo que "ambos lados" de cada segmento están realmente divididos.
Una vez que hemos construido la (s) lista (s) de segmentos, comenzamos a contar cuadrados. Para cada combinación de cuatro segmentos (particularmente, dos segmentos horizontales y dos verticales), probamos si forman un cuadrado. Además, verificamos que no hay vértices dentro de este cuadrado (lo que puede suceder si, por ejemplo, tenemos un cuadrado pequeño dentro de uno más grande). Esto nos da la cantidad deseada. Tenga en cuenta que aunque el programa prueba cada combinación cuatro veces en diferentes órdenes, el orden particular de las coordenadas del segmento garantiza que contamos cada cuadrado solo una vez.
fuente
itertools
para los bucles pero terminó siendo más largo. Puedo reducir algunos bytes conexec
reemplazos de cadena +, pero nada demasiado emocionante.Haskell,
276 266 250 237 225 222217 bytesSe vuelve cada vez más corto ... y más ofuscado.
Evaluar
n [(0,0,5,5),(6,8,10,4),(14,16,11,13),(19,1,18,2)]
para el primer caso de prueba. Creo que me estoy acercando a los límites del golf de este algoritmo en Haskell.Esta función es tan lenta (al menos O (n 3 ) donde n es el perímetro total de todos los rectángulos en la entrada) que no puedo evaluarla en los últimos dos casos de prueba. Cuando lo compilé con las optimizaciones activadas y lo ejecuté en la versión 400 veces reducida
[(0,249,250,0),(2,1,357,714)]
de la última prueba, terminó en poco más de 12 segundos. En base a esto, el caso de prueba real terminaría en unos 25 años.Explicación (parcial, expandiré esto cuando tenga tiempo)
Primero construimos dos listas
h
y de lav
siguiente manera. Para cada rectángulo en la entrada, dividimos su borde en segmentos de longitud 1. Los puntos finales oeste de los segmentos horizontales se almacenan enh
, y los puntos extremos sur de los segmentos verticales env
, como listas[x,y]
de longitud 2. Las coordenadasv
se almacenan en un reverso forma como[y,x]
por razones de golf. Luego, recorremos ambas listas y buscamos el borde horizontal[x,j]
y el borde vertical de[i,y]
manera quex < i
yi-x == j-y
(de modo que sean las esquinas noroeste y sureste de un cuadrado), y verifiquemos que los bordes del cuadrado estén en las listas correctash
yv
, mientras que el interior las coordenadas no lo son. El número de instancias positivas de la búsqueda es la salida.fuente