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


Statement
 

pdf   zip

thehtml

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 ‍
Public test cases
  • Input

    1 4
    2
    4 8
    2 7
    3
    0 6
    0 5
    2 9
    2
    1 3
    3 5
    2
    0 1
    2 3
    

    Output

    3
    3
    0
    0
    
  • Input

    2 3
    2
    1 4 7 6
    5 2 8 8
    2
    0 0 10 10
    -2 2 12 8
    4
    -215 -238 166 191
    -84 -131 200 11
    -38 13 32 190
    -2 -11 221 209

    Output

    4
    60
    0
    
  • Input

    3 1
    5
    3 -11 -75 145 330 116
    -167 -228 -62 60 56 29
    -109 -89 -283 256 130 47
    -44 -11 -151 24 285 108
    -242 -79 -302 364 192 297
    

    Output

    128037
    
  • Information
    Author
    Omer Giménez
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++ Python