시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 5 1 1 100.000%

문제

연종이는 자신의 마당에 새로운 감시 시스템을 설치하려고 한다.

연종이의 마당에는 N개의 원형 물체가 있다. 감시 시스템의 경계에는 고압 울타리를 설치하려고 한다. 울타리 안의 모든 보안 지역은 연결되어 있어야 한다. 또, 모든 물체는 보안 지역 안에 있어야 한다. 모든 물체는 서로 겹치거나 접하지 않는다. 이 때, 울타리의 길이를 최소로 하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 C (0 ≤ C ≤ 100)가 주어진다. 각 테스트 케이스의 첫째 줄에는 물체의 개수 N (0 < N ≤ 25)이 주어진다. 다음 N개의 줄에는 각 물체를 나타내는 세 개의 숫자 xi, yi, ri가 주어진다. i번째 물체의 중심 좌표는 (xi, yi)이며, 반지름은 ri이다. (|xi|, |yi| ≤ 100, 0 < ri ≤ 100)

출력

각 테스트 케이스에 대해서 모든 물체를 포함하는 울타리 길이의 최소값을 출력한다. 정답과의 오차는 10-7까지 허용한다.

예제 입력 1

3
3
2 2 1
8 2 1
5 6 1
2
6 4 2
2 4 1
4
2 2 2
6 1 1
5 5 2
1 6 1

예제 출력 1

22.2831853072
17.6761051635
25.4247779608
W3sicHJvYmxlbV9pZCI6IjM5NzAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NDhcdWM4MDQgXHVhZDZjXHVjNWVkIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1ZjBcdWM4ODVcdWM3NzRcdWIyOTQgXHVjNzkwXHVjMmUwXHVjNzU4IFx1YjljOFx1YjJmOVx1YzVkMCBcdWMwYzhcdWI4NWNcdWM2YjQgXHVhYzEwXHVjMmRjIFx1YzJkY1x1YzJhNFx1ZDE1Y1x1Yzc0NCBcdWMxMjRcdWNlNThcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG5cclxuXHJcbjxwPlx1YzVmMFx1Yzg4NVx1Yzc3NFx1Yzc1OCBcdWI5YzhcdWIyZjlcdWM1ZDBcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWM2ZDBcdWQ2MTUgXHViYjNjXHVjY2I0XHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVhYzEwXHVjMmRjIFx1YzJkY1x1YzJhNFx1ZDE1Y1x1Yzc1OCBcdWFjYmRcdWFjYzRcdWM1ZDBcdWIyOTQgXHVhY2UwXHVjNTU1IFx1YzZiOFx1ZDBjMFx1YjlhY1x1Yjk3YyBcdWMxMjRcdWNlNThcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM2YjhcdWQwYzBcdWI5YWMgXHVjNTQ4XHVjNzU4IFx1YmFhOFx1YjRlMCBcdWJjZjRcdWM1NDggXHVjOWMwXHVjNWVkXHVjNzQwIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWI2MTAsIFx1YmFhOFx1YjRlMCBcdWJiM2NcdWNjYjRcdWIyOTQgXHViY2Y0XHVjNTQ4IFx1YzljMFx1YzVlZCBcdWM1NDhcdWM1ZDAgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViYWE4XHViNGUwIFx1YmIzY1x1Y2NiNFx1YjI5NCBcdWMxMWNcdWI4NWMgXHVhY2I5XHVjZTU4XHVhYzcwXHViMDk4IFx1YzgxMVx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1YzZiOFx1ZDBjMFx1YjlhY1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjZDVjXHVjMThjXHViODVjIFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZmVuY2UucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTg1cHg7IHdpZHRoOjUyMnB4XCIgXC8+PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IEMgKDAgJmxlOyBDICZsZTsgMTAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYjNjXHVjY2I0XHVjNzU4IFx1YWMxY1x1YzIxOCBOICgwICZsdDsgTiAmbGU7IDI1KVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHViYjNjXHVjY2I0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWMxMzggXHVhYzFjXHVjNzU4IFx1YzIyYlx1Yzc5MCB4PHN1Yj5pPFwvc3ViPiwgeTxzdWI+aTxcL3N1Yj4sIHI8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gaVx1YmM4OFx1YzlmOCBcdWJiM2NcdWNjYjRcdWM3NTggXHVjOTExXHVjMmVjIFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCAoeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+KVx1Yzc3NFx1YmE3MCwgXHViYzE4XHVjOWMwXHViOTg0XHVjNzQwIHI8c3ViPmk8XC9zdWI+XHVjNzc0XHViMmU0LiAofHg8c3ViPmk8XC9zdWI+fCwgfHk8c3ViPmk8XC9zdWI+fCAmbGU7IDEwMCwgMCAmbHQ7IHI8c3ViPmk8XC9zdWI+ICZsZTsgMTAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWJhYThcdWI0ZTAgXHViYjNjXHVjY2I0XHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YjI5NCBcdWM2YjhcdWQwYzBcdWI5YWMgXHVhZTM4XHVjNzc0XHVjNzU4IFx1Y2Q1Y1x1YzE4Y1x1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzgxNVx1YjJmNVx1YWNmY1x1Yzc1OCBcdWM2MjRcdWNjMjhcdWIyOTQgMTA8c3VwPi03PFwvc3VwPlx1YWU0Y1x1YzljMCBcdWQ1YzhcdWM2YTlcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzk3MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNlY3VyaXR5IFpvbmUiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBtYW5hZ2VyIG9mIGEgbGFyZ2Ugc2VjdXJpdHkgY29tcGFueSBoYXMgdG8gYnVpbGQgYSBuZXcgc3VydmVpbGxhbmNlIHN5c3RlbSBmb3IgZGlmZmVyZW50IHNpdGVzLiBBIHNpdGUgY29uc2lzdHMgb2YgTiBvYmplY3RzIHdoZXJlIGVhY2ggb2JqZWN0IGhhcyBpdHMgb3duIHNlY3VyaXR5IGNpcmNsZS4gQXQgdGhlIGJvcmRlciBvZiB0aGUgc3VydmVpbGxhbmNlIHN5c3RlbSBhIGhpZ2ggdm9sdGFnZSBmZW5jZSBoYXMgdG8gYmUgaW5zdGFsbGVkLiBUaGUgc2VjdXJpdHkgem9uZSBpbnNpZGUgb2YgdGhlIGZlbmNlIGhhcyB0byBiZSBjb25uZWN0ZWQuIEZ1cnRoZXJtb3JlLCBhbGwgb2JqZWN0cyBhbmQgdGhlaXIgc2VjdXJpdHkgY2lyY2xlcyBzaG91bGQgYmUgaW5zaWRlIHRoZSBzZWN1cml0eSB6b25lLiBUaGUgc2VjdXJpdHkgY2lyY2xlcyBvZiBkaWZmZXJlbnQgb2JqZWN0cyB3aWxsIG5ldmVyIG92ZXJsYXAgb3IgdG91Y2guIE5vdyB0aGUgbWFuYWdlciBuZWVkcyB5b3VyIGhlbHAuIEhlIGFza3MgeW91IGZvciB0aGUgbWluaW1hbCBuZWVkZWQgZmVuY2UgbGVuZ3RoLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2ZlbmNlLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE4NXB4OyB3aWR0aDo1MjJweFwiIFwvPjxcL3A+XHJcblxyXG48cD5GaWd1cmUgMSAtIElsbHVzdHJhdGlvbiBvZiBmaXJzdCBhbmQgc2Vjb25kIHNhbXBsZSBpbnB1dC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBnaXZlcyB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgQyZuYnNwOygwICZsZTsgQyAmbGU7IDEwMCkuIFRoZSBmaXJzdCBsaW5lIG9mIGVhY2ggc3VjaCB0ZXN0IGNhc2UgaG9sZHMgdGhlIGludGVnZXIgTjogdGhlIG51bWJlciBvZiBvYmplY3RzIGluIHRoZSBjdXJyZW50IHNpdGUgKDAgJmx0OyBOIFx1MDAxNCAyNSkuIEVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGhvbGRzIHRocmVlIGludGVnZXJzICZuYnNwO3g8c3ViPmk8XC9zdWI+LCB5PHN1Yj5pPFwvc3ViPiwgYW5kIHI8c3ViPmk8XC9zdWI+IHRoYXQgZGVzY3JpYmUgYW4gb2JqZWN0LiBUaGUgY29vcmRpbmF0ZXMgb2YgdGhlIGktdGggb2JqZWN0IGFuZCB0aGUgcmFkaXVzIGZvciB0aGUgbmVlZGVkIHNlY3VyaXR5IGNpcmNsZSBmb3IgdGhpcyBvYmplY3QuICh8eDxzdWI+aTxcL3N1Yj58LCB8eTxzdWI+aTxcL3N1Yj58ICZsZTsgMTAwLCAwICZsdDsgcjxzdWI+aTxcL3N1Yj4mbmJzcDsmbGU7IDEwMCkmbmJzcDsoVGhlIGNlbnRlciBvZiB0aGUgc2VjdXJpdHkgY2lyY2xlIGFyb3VuZCBhbiBvYmplY3QgaXMgdGhlIHBvc2l0aW9uIG9mIHRoZSBvYmplY3QgaXRzZWxmLik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UgcHJpbnQgb25lIGxpbmUgY29udGFpbmluZyB0aGUgbWluaW1hbCBmZW5jZSBsZW5ndGggZm9yIHRoaXMgY2FzZS4gWW91ciBvdXRwdXQgc2hvdWxkIGhhdmUgYW4gYWJzb2x1dGUgb3IgcmVsYXRpdmUgZXJyb3Igb2YgYXQgbW9zdCAxMDxzdXA+LTc8XC9zdXA+LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==