ACM uses a new special technology of building its transceiver stations. This technology is called Modular Cuboid Architecture (MCA) and is covered by a patent of Lego company. All parts of the transceiver are shipped in unit blocks that have the form of cubes of exactly the same size. The cubes can be then connected to each other. The MCA is modular architecture, that means we can select preferred transceiver configuration and buy only those components we need .
The cubes must be always connected “face-to-face”, i.e. the whole side of one cube is connected to the whole side of another cube. One cube can be thus connected to at most six other units. The resulting equipment, consisting of unit cubes is called The Bulk in the communication technology slang.
Sometimes, an old and unneeded bulk is condemned, put into a storage place, and replaced with a new one. It was recently found that ACM has many of such old bulks that just occupy space and are no longer needed. The director has decided that all such bulks must be disassembled to single pieces to save some space. Unfortunately, there is no documentation for the old bulks and nobody knows the exact number of pieces that form them. You are to write a computer program that takes the bulk description and computes the number of unit cubes.
Each bulk is described by its faces (sides). A special X-ray based machine was constructed that is able to localise all faces of the bulk in the space, even the inner faces, because the bulk can be partially hollow (it can contain empty spaces inside). But any bulk must be connected (i.e. it cannot drop into two pieces) and composed of whole unit cubes.
Input
There is a single positive integer T on the first line of input (equal to about 1000). It stands for the number of bulks to follow. Each bulk description begins with a line containing single positive integer F, 6 <= F <= 250, stating the number of faces. Then there are F lines, each containing one face description. All faces of the bulk are always listed, in any order. Any face may be divided into several distinct parts and described like if it was more faces. Faces do not overlap. Every face has one inner side and one outer side. No side can be “partially inner and partially outer”.
Each face is described on a single line. The line begins with an integer number P stating the number of points that determine the face, 4 <= P <= 200. Then there are 3 x P numbers, coordinates of the points. Each point is described by three coordinates X,Y,Z (0 <= X,Y,Z <= 1000) separated by spaces. The points are separated from each other and from the number P by two space characters. These additional spaces were added to make the input more human readable. The face can be constructed by connecting the points in the specified order, plus connecting the last point with the first one.
The face is always composed of “unit squares”, that means every edge runs either in X, Y or Z-axis direction. If we take any two neighbouring points X1,Y1,Z1 and X2,Y2,Z2, then the points will always differ in exactly one of the three coordinates. I.e. it is either X1 <> X2, or Y1 <> Y2, or Z1 <> Z2, other two coordinates are the same. Every face lies in an orthogonal plane, i.e. exactly one coordinate is always the same for all points of the face. The face outline will never touch nor cross itself.
Output
Your program must print a single line for every test case. The line must contain the sentence The bulk is composed of V units., where V is the volume of the bulk.
Example
Sample Input:
2 12 4 10 10 10 10 10 20 10 20 20 10 20 10 4 20 10 10 20 10 20 20 20 20 20 20 10 4 10 10 10 10 10 20 20 10 20 20 10 10 4 10 20 10 10 20 20 20 20 20 20 20 10 4 10 10 10 10 20 10 20 20 10 20 10 10 5 10 10 20 10 20 20 20 20 20 20 15 20 20 10 20 4 14 14 14 14 14 16 14 16 16 14 16 14 4 16 14 14 16 14 16 16 16 16 16 16 14 4 14 14 14 14 14 16 16 14 16 16 14 14 4 14 16 14 14 16 16 16 16 16 16 16 14 4 14 14 14 14 16 14 16 16 14 16 14 14 4 14 14 16 14 16 16 16 16 16 16 14 16 12 4 20 20 30 20 30 30 30 30 30 30 20 30 4 10 10 10 10 40 10 40 40 10 40 10 10 6 10 10 20 20 10 20 20 30 20 30 30 20 30 40 20 10 40 20 6 20 10 20 20 20 20 30 20 20 30 40 20 40 40 20 40 10 20 4 10 10 10 40 10 10 40 10 20 10 10 20 4 10 40 10 40 40 10 40 40 20 10 40 20 4 20 20 20 30 20 20 30 20 30 20 20 30 4 20 30 20 30 30 20 30 30 30 20 30 30 4 10 10 10 10 40 10 10 40 20 10 10 20 4 40 10 10 40 40 10 40 40 20 40 10 20 4 20 20 20 20 30 20 20 30 30 20 20 30 4 30 20 20 30 30 20 30 30 30 30 20 30
Sample Output:
The bulk is composed of 992 units. The bulk is composed of 10000 units.
Warning: large Input/Output data, be careful with certain languages
Solution below . . .
Solution
This is a hard problem. 🙂 I found a hint online, which helped provide a direction, although I dropped Step 2, moved Step 5 before Step 3, added some additional computations, and replaced Step 4 because I didn’t understand it.
It may help to look at models of the sample input data.
1. Read input data into an array of faces, ignoring faces not perpendicular to the Z axis.
I.e., ignore faces where the Z coordinate is not the same for all points. Alternatively, we could use the X axis or the Y axis. We just want to work with a set of parallel planes. The problem description guarantees that they’ll be connected with perpendicular planes. We’re given the height of the planes (the Z coordinate) and that’s all we need for the volume calculation.
2. Compute the area of each face.
3. Identify each face as clockwise or counterclockwise.
Input coordinates are contiguous points. Depending on their order, each face is “drawn” clockwise or counterclockwise.
4. Find the bottom left point for each face.
Meaning the minimum X and Y coordinates. We need this in Step 6.
5. Sort array of faces by Z coordinate.
Giving us a “bottom up” array of parallel faces.
6. Compute the sign of each face based on whether it contributes to positive or negative volume.
A face with empty space under it contributes to negative volume. So we start with the bottom face and assign a negative sign. The moving “up” through the array of faces, the sign of each face will be the opposite of the nearest face below that completely covers it.
To find a “covering” face, look at the bottom left point of the face to be covered (from Step 4). Then find the nearest horizontal edge (parallel to X axis), if any, of the possible covering face that is at or below the bottom left point (i.e., Y coordinate of edge <= Y coordinate of bottom left point). Finally, check the clockwise orientation of the possible covering face to make sure that it’s drawn up and over the face to be covered.
7. Volume contributed by each face = area * height (Z coordinate) * sign.
8. Answer is sum of volumes from Step 7.
import java.util.Arrays;
import java.util.Scanner;
class Main {
static Face[] faces;
static boolean Overlaps(int index, int bottomLeftX, int bottomLeftY) {
int maxy = -99;
boolean result = false;
for (int i = 0; i < faces[index].size; i++) {
int last = (i == faces[index].size - 1) ? 0 : i + 1;
int minx, maxx, y;
// skip vertical edges
if (faces[index].x[i] == faces[index].x[last])
continue;
y = faces[index].y[i];
minx = Math.min(faces[index].x[i], faces[index].x[last]);
maxx = Math.max(faces[index].x[i], faces[index].x[last]);
if (bottomLeftY < y || y < maxy || bottomLeftX < minx || bottomLeftX >= maxx)
continue;
result = (faces[index].x[i] < faces[index].x[last]) ^ faces[index].clockwise; maxy = y; } return result; } static int FindCovering(int bottomLeftX, int bottomLeftY, int startindex) { int i; int level = faces[startindex].z[0]; // skip faces at the same level for (i = startindex; i >= 0 && faces[i].z[0] == level; i--);
// go through faces top down and find first that overlaps
// with given one
for (; i >= 0; i--) {
if (Overlaps(i, bottomLeftX, bottomLeftY))
return i;
}
return -1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while (T-- > 0) {
int F = sc.nextInt();
faces = new Face[F];
int faceCount = 0;
for (int i = 0; i < F; i++) {
int size = sc.nextInt();
Face f = new Face(size);
boolean need = true;
for (int j = 0; j < size; j++) { f.x[j] = sc.nextInt(); f.y[j] = sc.nextInt(); f.z[j] = sc.nextInt(); if (j > 0 && f.z[j] != f.z[j - 1])
need = false;
}
if (!need)
continue;
// compute area of face
// this is a simplified area computation that works
// because we are guaranteed that contiguous points will
// only differ in one coordinate.
f.area = 0;
for (int j = 0; j < size; j++) { int last = (j == size - 1) ? 0 : j + 1; if (f.x[j] == f.x[last]) continue; f.area += f.y[j] * (f.x[last] - f.x[j]); } // if area is greater than 0 then the order in which // the coordinates appear in the input is clockwise if (f.area > 0)
f.clockwise = true;
else {
f.clockwise = false;
f.area = -f.area;
}
/* find lower left point of face */
int o = 0;
for (int j = 1; j < f.size; j++) {
if (f.y[j] < f.y[o] || (f.y[j] == f.y[o] && f.x[j] < f.x[o]))
o = j;
}
f.bottomLeftX = f.x[o];
f.bottomLeftY = f.y[o];
faces[faceCount] = f;
faceCount++;
}
// sort faces according their levels
Arrays.sort(faces, 0, faceCount);
// for each face, find the face "above" (relative to z axis)
// that covers it
for (int i = 0; i < faceCount; i++) {
int hit =
FindCovering(faces[i].bottomLeftX, faces[i].bottomLeftY, i);
if (hit == -1)
// this will be true for the "lowest" face
faces[i].sign = -1;
else
// otherwise, flip the sign for the covering face
faces[i].sign = -faces[hit].sign;
}
// compute the volume
long volume = 0;
for (int i = 0; i < faceCount; i++) {
volume += faces[i].area * faces[i].z[0] * faces[i].sign;
}
System.out.printf("The bulk is composed of %d units.\n", volume);
}
sc.close();
}
}
class Face implements Comparable<Face> {
boolean clockwise;
int area;
int bottomLeftX;
int bottomLeftY;
int size;
int sign;
int[] x, y, z;
public Face(int size) {
this.size = size;
x = new int[size];
y = new int[size];
z = new int[size];
}
@Override
public int compareTo(Face o) {
return z[0] - o.z[0];
}
}
Please help! I can’t understand the problem