Electric Wiring
|
Bill is designing electric wiring for his new house. First of all, he has fixed the positions of several electrical outlets on the walls. To neatly connect any pair of outlets, he would make sure that the wire is always imbedded in the walls or the floor, and is parallel to at least one side of the wall. Naturally he wants to minimize the total length of wire he must buy to have all the outlets connected. |
|
By the way, do not forget that there is a door for every room. The wire must not cross the door. Figure 1 shows a possible setting in a room with 4 outlets.
Input Specification:
Your program must read test cases from a file “input.txt”. The input file consists of several test cases. For each test case, the first line contains 4 triples (x1, y1, z1) ... (x4, y4, z4) which are the coordinates of the four corners of a rectangular door. The second line contains size of the room, (Lx, Ly, Lz), and a positive integer N (<=20). Then N lines of coordinates (xi, yi, zi) of the outlets follow. Proceed until the end of file.
It is assumed that the cuboid room is completely in the first quadrant of the Cartesian coordinates with one of its corners at the origin, and the floor sits in x-y plane. It is guaranteed that each outlet belongs to one and only one of the four walls and no outlet is placed on the door. The two ends of a segment of wire must connect to outlets only.
Output Specification:
For each test case, output to a file “output.txt” in one line the nearest integer length of wire which can have all the outlets connected.
Sample Input:
0 0 0 0 0 3 1.5 0 0 1.5 0 3
10 10 10 4
0 1 3.3
2.5 0 2
5 0 0.8
5 10 1
Sample Output:
21
Hint: Take each outlet as a node in a graph. Implement a greedy algorithm to find the minimum spanning tree.
拜谢了!!
