ELC - Electrification
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.
Input
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]
Output
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.
Score
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.
Example
Input: 1 4 1.0 1.0 1.0 11.0 11.0 1.0 11.0 11.0 Output: 1 6.0 6.0 4 0 4 1 4 2 4 4 3
Score:
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 |
Date: | 2006-04-12 |
Time limit: | 2s |
Source limit: | 60000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO |
Resource: | ZCon 2007 |