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