시간 제한
메모리 제한
시간 제한
1초
메모리 제한
128 MB
하나의 장치는 크기가 모두 같은 단위 정육면체들을 이어 붙여 만든다. 정육면체는 항상 면과 면을 맞대어 연결한다. 즉 한 정육면체의 한 면 전체가 다른 정육면체의 한 면 전체와 맞닿으므로, 정육면체 하나는 최대 여섯 개의 다른 정육면체와 연결될 수 있다. 이렇게 연결된 단위 정육면체들의 덩어리를 벌크(bulk) 라고 부른다.
더 이상 필요 없는 오래된 벌크들을 공간 확보를 위해 낱개로 분해하려고 한다. 그런데 문서가 남아 있지 않아 각 벌크가 몇 개의 정육면체로 이루어져 있는지 아무도 모른다. 벌크의 설명이 주어질 때, 그 벌크를 이루는 단위 정육면체의 개수를 구하여라.
각 벌크는 그 면(face) 들로 설명된다. 스캐너는 벌크의 모든 면을 찾아내는데, 벌크가 속이 비어 있을 수 있으므로(내부에 빈 공간을 포함할 수 있다) 안쪽 면까지 모두 포함한다. 벌크는 항상 하나로 연결되어 있으며(두 조각으로 갈라지지 않는다) 온전한 단위 정육면체들로만 이루어져 있다.
첫 줄에는 벌크의 개수를 나타내는 양의 정수 T 가 주어진다.
각 벌크는 면의 개수 F (6≤F≤250) 가 적힌 한 줄로 시작하고, 이어서 면을 설명하는 F 개의 줄이 임의의 순서로 주어진다. 벌크의 모든 면이 나열된다. 하나의 면을 여러 부분으로 나누어 각각을 별개의 면처럼 적을 수도 있으며, 면끼리 겹치지는 않는다. 모든 면은 안쪽과 바깥쪽이 뚜렷이 구분되며, 한 면이 일부는 안쪽이고 일부는 바깥쪽인 경우는 없다.
각 면은 한 줄로 주어진다. 그 줄은 꼭짓점의 개수 P (4≤P≤200) 로 시작하고, 이어서 각 꼭짓점의 좌표 XYZ 를 나타내는 3P 개의 정수가 공백으로 구분되어 주어진다 (0≤X,Y,Z≤1000). 면은 주어진 순서대로 꼭짓점들을 잇고 마지막 꼭짓점을 다시 첫 꼭짓점과 이어 만든 닫힌 다각형이다.
모든 면은 단위 정사각형들로 이루어지므로 각 변은 X, Y, Z 축 중 하나에 평행하다. 즉 이웃한 두 꼭짓점은 정확히 한 좌표에서만 값이 다르다. 또한 모든 면은 축에 수직인 평면 위에 놓여 있어(면의 모든 꼭짓점에서 정확히 한 좌표가 항상 같다) 면의 외곽선은 자기 자신과 닿거나 교차하지 않는다.
각 벌크마다 한 줄에 The bulk is composed of V units. 를 출력한다. 여기서 V 는 벌크의 부피, 즉 벌크를 이루는 단위 정육면체의 개수이다.