#P1428. Hermes' Colony

Hermes' Colony

Description

Hermes, the Greek God of Speed, has created a two-dimensional colony Massilia in space. The colony, consisting of one or more provinces, can be represented by a linear equation in 3-dimensional 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 3-dimension like (x, y, z). All the x, y and z co-ordinates 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 co-ordinates of a city in that province.

Output

You 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.

-0.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
Province # 1 : 86.43
Province # 2 : 175.15

Source

Dhaka 2002