编程介的小学生 2017-03-03 03:10 采纳率: 20.5%
浏览 817
已采纳

Hermes' Colony

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.

Sample Input

-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

Sample Output

Province # 1 : 86.43
Province # 2 : 175.15

  • 写回答

2条回答 默认 最新

  • threenewbee 2017-03-07 21:02
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

悬赏问题

  • ¥15 下图接收小电路,谁知道原理
  • ¥15 装 pytorch 的时候出了好多问题,遇到这种情况怎么处理?
  • ¥20 IOS游览器某宝手机网页版自动立即购买JavaScript脚本
  • ¥15 手机接入宽带网线,如何释放宽带全部速度
  • ¥30 关于#r语言#的问题:如何对R语言中mfgarch包中构建的garch-midas模型进行样本内长期波动率预测和样本外长期波动率预测
  • ¥15 ETLCloud 处理json多层级问题
  • ¥15 matlab中使用gurobi时报错
  • ¥15 这个主板怎么能扩出一两个sata口
  • ¥15 不是,这到底错哪儿了😭
  • ¥15 2020长安杯与连接网探