ISLHOP - Island Hopping

The company Pacific Island Net (PIN) has identified several small island groups in the Pacific that do not have a fast internet connection. PIN plans to tap this potential market by offering internet service to the island inhabitants. Each groups of islands already has a deep-sea cable that connects the main island to the closest internet hub on the mainland (be it America, Australia or Asia). All that remains to be done is to connect the islands in a group to each other. You must write a program to help them determine a connection procedure.

For each island, you are given the position of its router and the number of island inhabitants. In the figure, the dark dots are the routers and the numbers are the numbers of inhabitants. PIN will build connections between pairs of routers such that every router has a path to the main island. PIN has decided to build the network such that the total amount of cable used is minimal. Under this restriction, there may be several optimal networks. However, it does not matter to PIN which of the optimal networks is built.

PIN is interested in the average time required for new customers to access the internet, based on the assumption that construction on all cable links in the network begins at the same time. Cable links can be constructed at a rate of one kilometer of cable per day. As a result, shorter cable links are completed before the longer links. An island will have internet access as soon as there is a path from the island to the main island along completed cable links. If mi is the number of inhabitants of the ith island and ti is the time when the island is connected to the internet, then the average connection time is:

Input

The input consists of several descriptions of groups of islands. The first line of each description contains a single positive integer n, the number of islands in the group (n <= 50). Each of the next n lines has three integers xi, yi, mi, giving the position of the router (xi, yi) and number of inhabitants mi(mi > 0) of the islands. Coordinates are measured in kilometers. The first island in this sequence is the main island.

The input is terminated by the number zero on a line by itself.

Output

For each group of islands in the input, output the sequence number of the group and the average number of days until the inhabitants are connected to the internet. The number of days should have two digits to the right of the decimal point. Use the output format in the sample given below.

Place a blank line after the output of each test case.

Example

Input:
7
11 12 2500
14 17 1500
9 9 750
7 15 600
19 16 500
8 18 400
15 21 250
0

Output:
Island Group: 1 Average 3.20

Added by:Fudan University Problem Setters
Date:2008-01-03
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ACM/ICPC World Final 2002 (unofficial testdata)

hide comments
2019-03-01 19:50:19
Are the inhabitants of the mainland counted in the total population for calculating the average? My answer sometimes is off by 0.1 - 0.2.
2015-10-26 14:38:59 Arya08
what is the range of xi , yi and mi(upper limit)
2013-10-21 21:39:45 Ashutosh Singla
There can be more than one, island at one position.
2011-04-07 06:18:48 :D
It can be proven than for every optimal network average connection time is the same. If you really want you can count the average average connection time over all optimal networks and it will also work :)
2009-06-28 06:18:32 Mostafa Saad
Output section is titled wrongly.

Edit by Blue Mary: Modified, thanks!

Last edit: 2009-06-28 06:18:51
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.