*Not an official ACM page*

[Problem G
| 1995 Western Europe problem set
| Ed's programming contest problem archive
| my home page]

### 1995-1996 ACM International Collegiate Programming Contest

Western European Regional

# 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