pascal 11665번 직육면체 교집합 (백준)

var i,n:int64;a,b:array[1..6]of int64; //변수
begin
readln(n); //n개의 직육면체
readln(b[1],b[2],b[3],b[4],b[5],b[6]); //첫번째 직육면체
for i:=2 to n do begin //2번째 부터의 직육면체
readln(a[1],a[2],a[3],a[4],a[5],a[6]); 
//직육면체들의 교집합은 직육면체, 이 교집합의 두 꼭짓점의 좌표들을 구합니다.
//좌표값이 작은 꼭짓점 구하기
if a[1]>b[1] then b[1]:=a[1];
if a[2]>b[2] then b[2]:=a[2];
if a[3]>b[3] then b[3]:=a[3];
//좌표값이 큰 꼭짓점 구하기
if a[4]<b[4] then b[4]:=a[4];
if a[5]<b[5] then b[5]:=a[5];
if a[6]<b[6] then b[6]:=a[6];
end;
//교집합의 x,y,z 의 길이 구하기
a[1]:=b[4]-b[1];
a[2]:=b[5]-b[2];
a[3]:=b[6]-b[3];
//만약 값이 음수라면 교집합은 양의 값에선 존재하지 않음 ---> 0으로 
if a[1]<0 then a[1]:=0;
if a[2]<0 then a[2]:=0;
if a[3]<0 then a[3]:=0;
write(a[1]*a[2]*a[3]); //교집합의 내적을 계산 후 출력
end.

 

풀이 : 기하학

 

문제에서는 x,y,z 의 값이 가장 작은 꼭짓점과, 가장 큰 꼭짓점 두개를 줍니다. (또한 좌표값들은 0 이상입니다)

여러 직육면체들의 교집합을 구하려면

1. 가장 작은 꼭짓점의 최댓값 (좌표)과

2. 가장 큰 꼭짓점의 최솟값 (좌표) 입니다.

 

위의 두 좌표를 이용하여 교집합의 x,y,z 축의 길이를 구할 수 있으며, 이 세 개의 값이 양수라면 교집합이 존재함을 알 수 있습니다.

 

ex)

 

3
1 1 1 7 7 7
2 3 4 7 8 9
4 3 2 9 8 7

 

블렌더로 해봤습니다.

이런식으로 포개져 있는 상태 입니다.

 

여기서 교집합은

1 1 1

2 3 4

4 3 2 의 최댓값인 4 3 4 을 가장 작은 좌표의 꼭짓점으로

 

7 7 7

7 8 9

9 8 7 의 최솟값인 777 을 가장 작은 좌표의 꼭짓점으로

 

한 직육면체 입니다.

 

 

이렇게 구한 꼭짓점들로 x,y,z 축의 길이를 구한다음, 교집합의 부피를 구할 수 있습니다.