페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#1931

[중등부] 2023 KOI 대비 모의고사 (4월 2주차)

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

문제

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

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

 

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

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

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

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

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

 

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

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


입력

입력은 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)를 정점으로 하는 직육면체임을 나타낸다.


출력

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


예제 #1

3 2

30 50 0 50 70 100

10 20 20 70 90 60

40 60 20 90 90 70
49000

예제 #2

1 1

0 0 0 1000000 1000000 1000000
1000000000000000000
로그인해야 코드를 작성할 수 있어요.