문제
오스트레일리아 대륙 서쪽에는 넓은 인도양이 펼쳐져 있다. 해양 연구가 JOI 씨는 인도양에 사는 \(N\)종류의 물고기 성질을 연구하고 있다. 각 종류마다 바다 속에 직육면체 모양의 서식 범위가 정해져 있다. 물고기는 경계를 포함해 서식 범위 안의 어느 곳이든 갈 수 있지만, 밖으로는 나가지 않는다. 바다 속 점은 실수 세 개 \((x, y, d)\)로 나타낸다. \((x, y, d)\)는 하늘에서 보았을 때 어떤 기준점에서 동쪽으로 \(x\), 북쪽으로 \(y\)만큼 간 위치이고, 해수면으로부터의 깊이가 \(d\)인 점이다. 해수면은 평면이라고 한다. JOI 씨는 \(K\)종류 이상의 물고기 서식 범위가 겹치는 곳이 얼마나 되는지 알고 싶다. 그런 곳 전체의 부피를 구하는 프로그램을 작성하라. |
입력
입력은 다음 형식으로 주어진다.
\(N\) \(K\)
\(X_{1,1}\) \(Y_{1,1}\) \(D_{1,1}\) \(X_{1,2}\) \(Y_{1,2}\) \(D_{1,2}\)
\(\vdots\)
\(X_{N,1}\) \(Y_{N,1}\) \(D_{N,1}\) \(X_{N,2}\) \(Y_{N,2}\) \(D_{N,2}\)
- 입력은 \(1+N\)줄이다.
- 첫째 줄에 정수 \(N\), \(K\)가 공백 하나로 구분되어 주어진다. 물고기가 \(N\)종류이고, \(K\)종류 이상이 겹치는 곳의 부피를 구하라는 뜻이다.
- 이어지는 \(N\)줄 가운데 \(i\)번째 줄(\(1 \le i \le N\))에는 정수 \(6\)개 \(X_{i,1}\), \(Y_{i,1}\), \(D_{i,1}\), \(X_{i,2}\), \(Y_{i,2}\), \(D_{i,2}\)가 공백 하나로 구분되어 주어진다. \(i\)번째 종류의 서식 범위는 여덟 점 \((X_{i,1}, Y_{i,1}, D_{i,1})\), \((X_{i,2}, Y_{i,1}, D_{i,1})\), \((X_{i,2}, Y_{i,2}, D_{i,1})\), \((X_{i,1}, Y_{i,2}, D_{i,1})\), \((X_{i,1}, Y_{i,1}, D_{i,2})\), \((X_{i,2}, Y_{i,1}, D_{i,2})\), \((X_{i,2}, Y_{i,2}, D_{i,2})\), \((X_{i,1}, Y_{i,2}, D_{i,2})\)를 꼭짓점으로 하는 직육면체이다.
- \(1 \le K \le N \le 50\)
- \(0 \le X_{i,1} \lt X_{i,2} \le 1000000\)
- \(0 \le Y_{i,1} \lt Y_{i,2} \le 1000000\)
- \(0 \le D_{i,1} \lt D_{i,2} \le 1000000\)
- 입력되는 값은 모두 정수이다.
출력
다음 형식으로 출력한다.
첫째 줄에 \(K\)종류 이상의 물고기 서식 범위가 겹치는 곳 전체의 부피를 출력한다.
예시 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)\)는 \(1\)번째와 \(3\)번째 종류의 서식 범위이므로 조건을 만족한다. 점 \((25, 35, 45)\)는 \(2\)번째 종류만의 서식 범위이므로 조건을 만족하지 않는다.
예시 2
입력
1 1
0 0 0 1000000 1000000 1000000
출력
1000000000000000000