Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Hermes' Colony
Time Limit: 1000MSMemory Limit: 10000K
Total Submissions: 325Accepted: 42


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.


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.


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.

Sample Input

-0.126826 -0.780330 0.612372 3.000000
11.593475 -0.702393 6.405027
-43.361881 -34.677124 -48.269711
-0.380480 -2.340990 1.837117
-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 Output

Province # 1 : 86.43
Province # 2 : 175.15


[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator