shunfurh 于 2017.09.15 09:53 提问
 Hermes' Colony

Description
Hermes, the Greek God of Speed, has created a twodimensional colony Massilia in space. The colony, consisting of one or more provinces, can be represented by a linear equation in 3dimensional space. In each province there are 3 or 4 cities, each being on their convex hull. Now, citizens of each province want to create road network connecting cities of their own province. Unfortunately, materials for road construction are not available in the colony, and can only be transported from Earth. Total material required to construct the roads will be proportional to their length. This is why they are interested to build road networks of shortest length connecting different cities of a province. In order to minimize length of each network they are also ready to make junctions away from cities, if so required.
Unfortunately creatures of the colony are pretty weak in mathematics and algorithms. They have, therefore, decided to take services of homo sapiens of earth, who are believed to be good in mathematics and algorithms. Accordingly the chief of Massilia sent an email to Academy of Computers and Mathematics(ACM) with Head Quarters at Dhaka to solve the problem. ACM has now asked you to help out our friends in Massilia.
Input
The colony is described by an equation ax+by+cz=d. There are N provinces in the colony. A city in a province can be described by a point in 3dimension like (x, y, z). All the x, y and z coordinates will be within 100.00 and +100.00. The first line of input will contain a, b, c and d. Then the number of provinces (N) in the colony will be given in the second line. The remaining lines will describe each province one by one.
The description of a province starts with the number of cities M (3 <= M <= 4) in the province in a line followed by M lines. Each line contains 3 numbers describing respectively the x, y and z coordinates of a city in that province.
OutputYou should print one line for each province in the input data as follows:
Province # p : L
Where p is the serial number of the province as they appear in the input. 1 <= p <= N, and L is the minimum length of the road network for that province. L should contain two digits after the decimal point and should be exact up to 2 decimal points.
Sample Input0.126826 0.780330 0.612372 3.000000
2
3
11.593475 0.702393 6.405027
43.361881 34.677124 48.269711
0.380480 2.340990 1.837117
4
15.033179 6.549108 10.130860
13.950171 53.592907 66.282234
49.017246 0.979824 16.299353
46.824024 12.971205 31.125420
Sample OutputProvince # 1 : 86.43
Province # 2 : 175.15