Intersección 1D, 2D y 3D P84229

Se te pide que calcules el tamaño de la intersección de intervalos (1D), rectangulos (2D) y paralelepípedos (3D). En concreto:

• Intervalos (1D). Calcula el tamaño del intervalo intersección de varios intervalos. Por ejemplo, la intersección de $[4,8]$ y $[2,7]$ es el intervalo $[4,7]$, de tamaño $7-4=3$. La intersección de los intervalos $[0,6]$, $[0, 5]$ y $[2,9]$ es el intervalo $[2,5]$, y su tamaño es $5-2 = 3$; la intersección de $[1,3]$ y $[3,5]$ es $[3,3]$, y su tamaño es $0$; la intersección de $[0,1]$ y $[2,3]$ es el conjunto vacío, cuyo tamaño también es $0$.

  (0,-0.2)(10,0.9) (0,-0.2)(10,0.9) (4,0)(8,1) (2,0)(7,1) (4,0)(7,1)

• Rectángulos (2D). Calcula el área del rectángulo que resulta de la intersección de varios rectángulos. Por ejemplo, la intersección del rectángulo de esquinas $(1,4)$ y $(7,6)$, con el rectángulo de esquinas $(5,2)$ y $(8, 8)$ es el rectángulo de esquinas $(5,4)$ y $(7,6)$, cuyo tamaño (área) es $(7-5)\cdot(6-4)=4$.

  (0,0)(10,10) (0,0)(10,10) (1,4)(7,6) (5,2)(8,8) (5,4)(7,6)

• Paralelepípedos (3D). Calcula el volumen del paralelepípedo que resulta de la intersección de varios paralelepípedos.

Entrada

La entrada consiste en dos números $D$ y $n$. El número $D$, que es $1$, $2$ o $3$, indica la dimensión de los $n\leq 100$ casos que siguen. Cada caso se describe en varias líneas. La primera línea contiene el número $k$ de objetos (intervalos, rectángulos o paralelepípedos) a intersecar. A continuación, $k$ líneas de $2D$ números cada una, para describir los $k$ objetos. Cada objeto se describe con 2 puntos de $D$ coordenadas, todas ellas entre $-500$ y $500$. El primer punto es el punto del objeto con coordenadas menores (esquina inferior izquierda en el caso de rectángulos) y el segundo el de coordenadas mayores (esquina superior derecha).

Salida

Para cada caso, escribe en una línea el tamaño de la intersección.

Puntuación

• Test1:   Pruebas con $k=2$ intervalos ($D=1$).

• Test2:   Pruebas con $k\leq 100$ intervalos ($D=1$).

• Test3:   Pruebas con $k\leq 100$ rectángulos ($D=2$).

• Test4:   Pruebas con $k\leq 100$ paralelepípedos ($D=3$).