JOI 2012/2013 예선 5- 물고기의 서식 범위 > 문제은행 : 정보올림피아드&알고리즘




1903 : 물고기의 서식 범위

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
1 회   
시도횟수
3 회   

문제

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

해양 연구원인 동현이는 인도양에 서식하고 있는 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 번째 종류의 물고기 서식 범위가 8점 (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 행으로 출력하라.


입력 예

3 2
30 50 0 50 70 100
10 20 20 70 90 60
40 60 20 90 90 70

출력 예

49000

입력 예

1 1
0 0 0 1000000 1000000 1000000

출력 예

1000000000000000000

Hint!

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

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

또한 물고기의 서식 범위는 아래 그림과 같이 되어있다. 

점 O는 해수면 기준 지점을 나타낸다.




경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP