ELC - Electrification

no tags 

We are trying to develop the electrical power infrastructure in the small country of Byteland. For this purpose not far from each city we have built a nuclear power plant (NPP). We have also connected the nearest house to this NPP with a cable. The goal of this project is to connect all houses of each city to the source of electricity. Each house already connected to electricity become a source of electricity. Since there is a severe shortage of electrical cable, the total length of the electricity network should be kept as small as possible. In some places we can set up transformer/splitter boxes to which we can potentially connect several cables; all their endpoints are then considered connected.


t – the number of cities; then follows the description of each of t cities. [t <= 50]
The description of each city begins with N - the number of houses in the city [3 <= N <= 3000]. Then exactly N lines follow, with two real numbers: x, y in each, representing the coordinates of a house. [0.0 <= x, y <= 10000.0]


For each test case you must output a connected electrical net, e.g. all houses must be connected with each other, directly, through other houses or through transformers. For each test output integer M [0 <= M <= N] - the number of required transformers. On each of following M lines output the coordinates of the transformers x, y [0.0 <= x, y <= 10000.0]. Next output the number K which is equal to the number of required cables [N+M-1 <= K <= (M+N)*(M+N-1)/2]. On the following K lines output two integers i, j - indexes of houses or transformers. Indexes for houses begins with 0 and end with N-1, indexes for transformers begin with N and end with N+M-1.


The score for the problem is given as: total_score = (200+time)*(score_1+score_2+...score_t)/200. In the above formula, score_i is equal to the length of the electrical cable used for electrification of the ith city, and time is the runtime of your solution.


1.0 1.0
1.0 11.0
11.0 1.0
11.0 11.0

6.0 6.0
0 4
1 4
2 4
4 3


Suppose that the solution ran for 10 seconds. The length of the cable is score_1 = 20*sqrt(2). In this case number of points awarded to the program will be equal to 29.698485.

Added by:Roman Sol
Time limit:2s
Source limit:60000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO
Resource:ZCon 2007