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

#6094

직육면체 교집합 부피 1s 1024MB

문제

직육면체의 부피는 밑변의 넓이와 높이를 곱한 값으로 계산이 가능하다.

N개의 직육면체가 있는데, i번째 직육면체의 한 꼭지점의 위치는 (sx_i, sy_i, sz_i)에 위치하고, 해당 꼭지점의 반대쪽 꼭지점의 위치는 (ex_i, ey_i, ez_i)에 위치한다.

N개의 직육면체의 정보들이 주어졌을 때, 모든 직육면체의 교집합에 해당하는 부피를 출력하는 프로그램을 작성하시오.


입력

첫 줄에 정수 N이 주어진다. (1 \le N \le 1,000)

두 번째 줄부터 N줄에 걸쳐 i번째 직육면체의 정보 sx_i, sy_i, sz_i, ex_i, ey_i, ez_i가 주어진다. (1 \le sx_i < ex_i \le 1,000, 1 \le sy_i < ey_i \le 1,000, 1 \le sz_i < ez_i \le 1,000)

직육면체의 모든 모서리는 축에 나란함이 보장된다. 즉, AABB(Axis-Aligned Bounding Box)문제임이 보장된다.


출력

첫 줄에 직육면체의 교집합에 해당하는 부피를 출력한다.


예제 #1

3
1 1 1 10 10 10
3 3 3 5 5 5
3 3 3 4 4 4
1

예제 #2

2
1 1 1 2 2 2
3 3 1 4 4 2
0

예제 #3

1
1 1 1 3 3 3
8
로그인해야 코드를 작성할 수 있어요.