Problem F

Islands

Now that the Eurotunnel between France and Great Britain is in operation, the French government is thinking about a new project to expand the connections with their British neighbors. Inspired by the movie "Bridges of Madison County," their prime architect Clouseau has been working on a plan to connect France to the Channel Islands by building a number of bridges.

To minimize the costs of the bridges, a necessity to get the plan approved, Clouseau has been working hard to find the best places to build the bridges that connect the islands to France. He has figured out that connecting each island to France individually is not the cheapest solution; it is cheaper to construct a bridge between one island and France, and build additional bridges to connect the other islands indirectly. Clouseau, however, is unable to find the best places to build the bridges because of the irregular shapes of the islands.

By approximating the islands as circles, Clouseau was able to report his boss, Mr. Dreyfus, an estimate of the length of the interconnecting bridges. Mr. Dreyfus, however, is not satisfied and demands that Clouseau report by Monday the exact length of the bridges needed based on the actual shapes of the Channel Islands. If Clouseau does not report on time he will be fired. Would you be so kind to help out Clouseau and write a program that computes the minimum length of the bridges needed to interconnect the Channel Islands?

Input Specification

The first line of input contains the number of test cases. A test case consists of one line holding the number of islands (2 <= N <= 100), followed by N lines that describe the islands. An island is a polygon, which is described as a number (1 <= P <= 25) that gives the number of points followed by P pairs of coordinates. Each coordinate is an integer in the range [-1000...1000]. The points are listed in order such that by connecting consecutive points, and the last point to the first, the perimeter of the island is given. It is guaranteed that islands do not touch or intersect.

Output Specification

For each test case output one line reporting the minimal interconnect as follows:

The minimal interconnect consists of N bridges with a total length of L

Where N is the number of bridges, and L is the total length, which should be printed as a floating point number with an accuracy of three digits.

Example Input

1
3
4 0 0 0 1 1 1 1 0
4 2 0 2 1 3 1 3 0
3 4 0 5 0 5 1

Example Output

The minimal interconnect consists of 2 bridges with a total length of 2.000

This page maintained by Ed Karrels.
Last updated January 3, 1998