Submit | All submissions | Best solutions | Back to list |

## ELASTIC - Elastic Bands |

The Institute of Circles with Perimetral Connections (ICPC) has recently discovered that

several machines that were working in their diverse productive areas were totally obsolete.

Of course, all machines in the Institute contain several circles.

The Supreme Chief Director Manager President of the ICPC asked their Computer Aided

Problem Solving department to help in overcoming this situation. They have signaled

you as the maximum responsible, so you better get to work.

Many machines in the Institute have mechanical parts in the shape of a circle that need

to be rotated clockwise in order for the machine to work. Currently, each circular part

is connected to a different electrical engine that does the job. You noted, however, that

when many circles are coplanar, you can connect them with elastic bands and they will

rotate all together with the energy of one engine.

This marvelous idea lead you to a new problem. What’s the optimal way to connect

all the circles? In general, there are many ways to place elastic bands and make all the

circles be connected. Since some of the rotating power of the system is lost in the tension

of the elastic bands, you want to minimize the total length of elastic bands used.

Formally, the length of the elastic band that connects two cricles is the perimeter of the

smallest convex area that contains both circles. The total length is the sum of the lengths

of all used elastic bands. Two circles can be connected with an elastic band even if the

band touches or goes through any number of other circles or elastic bands.

### Input

The input contains several test cases, each one described in several lines. The first line

contains an integer N indicating the number of circles to connect (2 ≤ N ≤ 3000). Each

of the next N lines describes a different circle using three integers X, Y and R separated

by single spaces (1 ≤ X, Y, R ≤ 10^{6} ). The values X and Y represent the coordinates of

the center of the circle in the XY plane, while the value R indicates its radius. You may

assume that within each test case no two circles overlap or touch each other. The last

line of the input contains a single −1 and should not be processed as a test case.

### Output

For each test case output a single line containing a real number representing the minimum

total length of elastic band needed to connect all the circles. Round the result to the

closest rational number with three decimal places. In case of ties, round up. Always use

exactly three digits after the decimal point, even if it means finishing with a zero.

### Example

Input:

3

2 2 2

1 6 1

6 1 1

2

1 1 1

1 4 1

-1Output:35.829

12.283

Added by: | Pablo Ariel Heiber |

Date: | 2010-08-22 |

Time limit: | 85.17s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | C C++ 4.3.2 CPP |

Resource: | FCEyN UBA ICPC Selection 2009 |