¿La página no carga? Prueba haciendo clic aquí.
Placeholder

#1903

물고기의 서식 범위 1s 64MB

Problemas

호주 대륙의 서쪽에는 넓은 인도양이 펼쳐져 있다. 

해양 연구원인 동현이는 인도양에 서식하고 있는 N 종류의 물고기의 특성에 대해 연구하고 있다.

각 물고기의 종류에 대해 바다에는 직육면체 모양의 서식 범위가 정해져 있다. 

물고기는 경계를 포함하여 서식 범위 안의 어느 곳에도 이동할 수 있지만 서식 범위 밖으로 나가는 것은 결코 아니다.

바다 가운데의 점은 3개의 실수 (x, y, d)로 다음과 같이 표현한다.

  • (x, y, d)는 상공에서 볼 때 어느 지점을 기준으로 동쪽으로 x, 북쪽으로 y 위치이며, 해수면에서의 깊이가 d 점을 나타낸다.

  • 해수면은 평면이라고 한다.

동현이는 K 종류 이상의 물고기 서식 범위가 겹치는 부피가 얼마나 되는지 알고 싶다. 

그런 장소 전체의 부피를 구하는 프로그램을 작성하시오.


Entrada

입력은 1 + N 행이 된다. 

첫 번째 줄에는 두 개의 정수 N, K (1 ≤ K ≤ N ≤ 50)가 공백을 기준으로 나누어 주어진다. 이것은 물고기가 N 종류이며, K 종류 이상의 물고기 서식 범위가 겹치는 위치의 부피를 구하고 싶은 것을 나타낸다.

마지막 N 행 중 i 번째 줄 (1 ≤ i ≤ N)에는 6개의 정수 Xi1, Yi1, Di1, Xi2, Yi2, Di2가 적혀있다. (0 ≤ Xi1 < Xi2 ≤ 106, 0 ≤ Yi1 < Yi2 ≤ 106, 0 ≤ Di1 < Di2 ≤ 106) 

이것은 i 번째 종류의 물고기 서식 범위가 여덟 개의 점 (Xi1, Yi1, Di1), (Xi2, Yi1, Di1), (Xi2, Yi2, Di1), (Xi1, Yi2, Di1),  (Xi1, Yi1, Di2), (Xi2, Yi1, Di2), (Xi2, Yi2, Di2), (Xi1, Yi2, Di2)을 꼭지점으로 하는 직육면체임을 나타낸다.


Salida

K 종류 이상의 물고기 서식 범위가 겹치는 위치 전체의 부피를 1 행으로 출력하라.


Ejemplo #1

3 2

30 50 0 50 70 100

10 20 20 70 90 60

40 60 20 90 90 70
49000

점 (45, 65, 65)는 첫 번째 종류의 물고기와 세 번째 종류의 물고기의 서식 범위가 있기 때문에 조건에 맞는 장소이다. 

반면, 점 (25, 35, 45)는 두 번째 종류의 물고기만의 서식 범위이기 때문에, 조건에 부합하는 장소가 아니다. 

물고기의 서식 범위는 아래 그림과 같이 나타낼 수 있다. 점 O는 원점이며 z=0 영역이 해수면을 의미한다.


Ejemplo #2

1 1

0 0 0 1000000 1000000 1000000
1000000000000000000


Fuente

JOI 2012/2013 예선 5

Debes iniciar sesión para escribir código.