시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblxyXG5cclxuXHJcbjxwPlx1YzVmMFx1Yzg4NVx1Yzc3NFx1Yzc1OCBcdWI5YzhcdWIyZjlcdWM1ZDBcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWM2ZDBcdWQ2MTUgXHViYjNjXHVjY2I0XHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVhYzEwXHVjMmRjIFx1YzJkY1x1YzJhNFx1ZDE1Y1x1Yzc1OCBcdWFjYmRcdWFjYzRcdWM1ZDBcdWIyOTQgXHVhY2UwXHVjNTU1IFx1YzZiOFx1ZDBjMFx1YjlhY1x1Yjk3YyBcdWMxMjRcdWNlNThcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM2YjhcdWQwYzBcdWI5YWMgXHVjNTQ4XHVjNzU4IFx1YmFhOFx1YjRlMCBcdWJjZjRcdWM1NDggXHVjOWMwXHVjNWVkXHVjNzQwIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWI2MTAsIFx1YmFhOFx1YjRlMCBcdWJiM2NcdWNjYjRcdWIyOTQgXHViY2Y0XHVjNTQ4IFx1YzljMFx1YzVlZCBcdWM1NDhcdWM1ZDAgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViYWE4XHViNGUwIFx1YmIzY1x1Y2NiNFx1YjI5NCBcdWMxMWNcdWI4NWMgXHVhY2I5XHVjZTU4XHVhYzcwXHViMDk4IFx1YzgxMVx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVjNmI4XHVkMGMwXHViOWFjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWNkNWNcdWMxOGNcdWI4NWMgXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcblxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9mZW5jZS5wbmdcIiBzdHlsZT1cImhlaWdodDoxODVweDsgd2lkdGg6NTIycHhcIiBcLz48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggQyAoMCAmbGU7IEMgJmxlOyAxMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJiM2NcdWNjYjRcdWM3NTggXHVhYzFjXHVjMjE4IE4gKDAgJmx0OyBOICZsZTsgMjUpXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWJiM2NcdWNjYjRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzEzOCBcdWFjMWNcdWM3NTggXHVjMjJiXHVjNzkwIHg8c3ViPmk8XC9zdWI+LCB5PHN1Yj5pPFwvc3ViPiwgcjxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBpXHViYzg4XHVjOWY4IFx1YmIzY1x1Y2NiNFx1Yzc1OCBcdWM5MTFcdWMyZWMgXHVjODhjXHVkNDVjXHViMjk0ICh4PHN1Yj5pPFwvc3ViPiwgeTxzdWI+aTxcL3N1Yj4pXHVjNzc0XHViYTcwLCBcdWJjMThcdWM5YzBcdWI5ODRcdWM3NDAgcjxzdWI+aTxcL3N1Yj5cdWM3NzRcdWIyZTQuICh8eDxzdWI+aTxcL3N1Yj58LCB8eTxzdWI+aTxcL3N1Yj58ICZsZTsgMTAwLCAwICZsdDsgcjxzdWI+aTxcL3N1Yj4gJmxlOyAxMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1YmFhOFx1YjRlMCBcdWJiM2NcdWNjYjRcdWI5N2MgXHVkM2VjXHVkNTY4XHVkNTU4XHViMjk0IFx1YzZiOFx1ZDBjMFx1YjlhYyBcdWFlMzhcdWM3NzRcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjODE1XHViMmY1XHVhY2ZjXHVjNzU4IFx1YzYyNFx1Y2MyOFx1YjI5NCAxMDxzdXA+LTc8XC9zdXA+XHVhZTRjXHVjOWMwIFx1ZDVjOFx1YzZhOVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzOTcwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU2VjdXJpdHkgWm9uZSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIG1hbmFnZXIgb2YgYSBsYXJnZSBzZWN1cml0eSBjb21wYW55IGhhcyB0byBidWlsZCBhIG5ldyBzdXJ2ZWlsbGFuY2Ugc3lzdGVtIGZvciBkaWZmZXJlbnQgc2l0ZXMuIEEgc2l0ZSBjb25zaXN0cyBvZiBOIG9iamVjdHMgd2hlcmUgZWFjaCBvYmplY3QgaGFzIGl0cyBvd24gc2VjdXJpdHkgY2lyY2xlLiBBdCB0aGUgYm9yZGVyIG9mIHRoZSBzdXJ2ZWlsbGFuY2Ugc3lzdGVtIGEgaGlnaCB2b2x0YWdlIGZlbmNlIGhhcyB0byBiZSBpbnN0YWxsZWQuIFRoZSBzZWN1cml0eSB6b25lIGluc2lkZSBvZiB0aGUgZmVuY2UgaGFzIHRvIGJlIGNvbm5lY3RlZC4gRnVydGhlcm1vcmUsIGFsbCBvYmplY3RzIGFuZCB0aGVpciBzZWN1cml0eSBjaXJjbGVzIHNob3VsZCBiZSBpbnNpZGUgdGhlIHNlY3VyaXR5IHpvbmUuIFRoZSBzZWN1cml0eSBjaXJjbGVzIG9mIGRpZmZlcmVudCBvYmplY3RzIHdpbGwgbmV2ZXIgb3ZlcmxhcCBvciB0b3VjaC4gTm93IHRoZSBtYW5hZ2VyIG5lZWRzIHlvdXIgaGVscC4gSGUgYXNrcyB5b3UgZm9yIHRoZSBtaW5pbWFsIG5lZWRlZCBmZW5jZSBsZW5ndGguPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZmVuY2UucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTg1cHg7IHdpZHRoOjUyMnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZpZ3VyZSAxIC0gSWxsdXN0cmF0aW9uIG9mIGZpcnN0IGFuZCBzZWNvbmQgc2FtcGxlIGlucHV0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGdpdmVzIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBDJm5ic3A7KDAgJmxlOyBDICZsZTsgMTAwKS4gVGhlIGZpcnN0IGxpbmUgb2YgZWFjaCBzdWNoIHRlc3QgY2FzZSBob2xkcyB0aGUgaW50ZWdlciBOOiB0aGUgbnVtYmVyIG9mIG9iamVjdHMgaW4gdGhlIGN1cnJlbnQgc2l0ZSAoMCAmbHQ7IE4gXHUwMDE0IDI1KS4gRWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgaG9sZHMgdGhyZWUgaW50ZWdlcnMgJm5ic3A7eDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+LCBhbmQgcjxzdWI+aTxcL3N1Yj4gdGhhdCBkZXNjcmliZSBhbiBvYmplY3QuIFRoZSBjb29yZGluYXRlcyBvZiB0aGUgaS10aCBvYmplY3QgYW5kIHRoZSByYWRpdXMgZm9yIHRoZSBuZWVkZWQgc2VjdXJpdHkgY2lyY2xlIGZvciB0aGlzIG9iamVjdC4gKHx4PHN1Yj5pPFwvc3ViPnwsIHx5PHN1Yj5pPFwvc3ViPnwgJmxlOyAxMDAsIDAgJmx0OyByPHN1Yj5pPFwvc3ViPiZuYnNwOyZsZTsgMTAwKSZuYnNwOyhUaGUgY2VudGVyIG9mIHRoZSBzZWN1cml0eSBjaXJjbGUgYXJvdW5kIGFuIG9iamVjdCBpcyB0aGUgcG9zaXRpb24gb2YgdGhlIG9iamVjdCBpdHNlbGYuKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSBwcmludCBvbmUgbGluZSBjb250YWluaW5nIHRoZSBtaW5pbWFsIGZlbmNlIGxlbmd0aCBmb3IgdGhpcyBjYXNlLiBZb3VyIG91dHB1dCBzaG91bGQgaGF2ZSBhbiBhYnNvbHV0ZSBvciByZWxhdGl2ZSBlcnJvciBvZiBhdCBtb3N0IDEwPHN1cD4tNzxcL3N1cD4uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d