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.
  unit=0.5cm (0,-0.2)(10,0.9) [subgriddiv=1,griddots=10,gridlabels=7pt](0,-0.2)(10,0.9) [linewidth=0.5pt,fillstyle=vlines,hatchwidth=0.4pt,hatchsep=1.5pt](4,0)(8,1) [linewidth=0.5pt,fillstyle=hlines](2,0)(7,1) [linewidth=2pt](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)·(6−4)=4.
  unit=0.5cm (0,0)(10,10) [subgriddiv=1,griddots=10,gridlabels=7pt](0,0)(10,10) [linewidth=0.5pt,fillstyle=vlines,hatchwidth=0.4pt,hatchsep=1.5pt](1,4)(7,6) [linewidth=0.5pt,fillstyle=hlines](5,2)(8,8) [linewidth=2pt](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≤ 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).  30 Puntos 

• Test2:   Pruebas con k≤ 100 intervalos (D=1).  20 Puntos 

• Test3:   Pruebas con k≤ 100 rectángulos (D=2).  25 Puntos 

• Test4:   Pruebas con k≤ 100 paralelepípedos (D=3).  25 Puntos