Crop Circle

Time Limit : 1 sec, Memory Limit : 65536 KB

Problem 07: Crop Circle

アルゼンチンの広大な農地に突如ミステリーサークルが出没した。ミステリーサークルは重なっているもの、ポツンとあるもの、大きいもの、小さいものと合計 n 個確認された。

あるミステリーハンターが空中からミステリーサークルの全体像を撮影しようと試みたところ、各円の輪郭がはっきりしていなかったため、映像にその美しい模様を映し出すことが難しいことが分かった。

そこで、そのミステリーハンターは輪郭に沿って特殊素材の紐を設置し、輪郭を強調する提案をした。

紐を設置する部分は、あるミステリーサークルの円周上で、他のどのミステリーサークルにも含まれない部分である。

撮影隊は必要な紐の長さを計測するために、プログラムの作成をあなたに依頼した。各ミステリーサークルの中心座標と半径を入力し、設置する紐の長さを報告するプログラムを作成せよ。

参考として入出力例の1つ目と2つ目のケースをそれぞれ図1、図2に示す。紐の部分が太い線で示されている。



図1




図2


Input

入力として複数のデータセットが与えられる。各データセットは以下の形式で与えられる:

n (ミステリーサークルの数:整数)
x1 y1 r1  (1 個目のサークルの中心座標と半径:空白区切りの実数)
x2 y2 r2  (2 個目のサークルの中心座標と半径:空白区切りの実数)
.
.
xn yn rn  (n 個目のサークルの中心座標と半径:空白区切りの実数)

n が 0 のとき、入力の終わりを示す。

Output

各データセットに対して、紐の長さを1行に出力せよ。出力は 0.000001 以下の誤差を含んでもよい。

Constraints

  • n ≤ 100
  • -1000 ≤ xi, yi ≤ 1000
  • 0 < ri ≤ 100

Sample Input

4
6 4 2
4 7 3
7 10 3
13 6 1
4
7 4 2
4 7 3
7 10 3
11 6 3
0

Output for the Sample Input

39.664699289572
45.627024663706

Source: PC Koshien 2009 Warm-Up Contest , Aizu-Wakamatsu, Japan, 2009-08-22
Problem Setter:  Takashi Tayama