28297번 - 차량 모듈 제작 스페셜 저지

문제

현대모비스는 한국 외에도 유럽, 중국, 미국, 인도 등 여러 곳에 연구소를 두고 자율주행, 전동화, 커넥티비티 등의 미래기술은 물론 기존 기계 부품(제동, 조향, 현가, 안전, 램프 등)에도 ICT 기술을 융합하여 다양한 연구 개발을 진행하고 있다.

현대모비스의 엔지니어 현모는 자신의 팀이 개발한 새로운 소프트웨어를 적용하기 위해 새로운 차량 모듈을 만들었다. 새로운 차량 모듈은 다음과 같은 원리로 동작한다.

• 차량 모듈 내부에는 기어가 $N$개 존재하고, 각각의 기어는 반지름이 $r_i$인 하나의 원으로 표현된다. $(1 \le i \le N,ドル $i$는 정수$)$
• 현모는 $N$개의 기어 중 1ドル$개를 선택해 모터와 연결할 수 있다. 모터와 연결된 기어는 차량 모듈의 전원을 켜면 회전한다.
• 2ドル$개의 기어 $a,ドル $b$에 대하여 $a$가 회전하고 있는 상태이고, $a$와 $b$가 접하거나 겹치면 $b$도 회전한다. 기어의 회전하는 방향은 고려하지 않는다.
• 2ドル$개의 기어 $a,ドル $b$를 벨트를 이용하여 연결할 수 있다. 2ドル$개의 기어 $a,ドル $b$에 대하여 $a$가 회전하고 있는 상태이고, $a$와 $b$가 벨트로 연결되어 있으면 $b$도 회전한다.
• 하나의 기어에 여러 벨트를 두를 수 있지만, 하나의 벨트로 3ドル$개 이상의 기어를 연결할 수 없다.
• 기어를 벨트로 연결했을 때 사용되는 벨트의 길이는 2ドル$개의 기어를 감싸는 가장 짧은 곡선의 길이다.
• 차량 모듈 내부에 있는 $N$개의 기어가 모두 회전한다면, 차량 모듈이 정상적으로 동작한다.

위 그림은 두 기어를 벨트로 연결한 모습의 그림이다.

현모는 차량 모듈의 전원을 켰을 때 정상적으로 동작할 수 있게 하려고 한다. 차량 모듈을 정상적으로 동작하게 하기 위해 필요한 벨트 길이의 총합의 최솟값을 구하시오.

입력

첫 번째 줄에 차량 모듈의 내부에 있는 기어의 개수를 나타내는 정수 $N$이 주어진다. $(1\le N\le 1,円 000)$

두 번째 줄부터 $N$개의 줄에 걸쳐 $N$개의 기어의 정보가 주어진다. 그중 $i$번째 줄에는 $i$번째 기어의 정보가 주어진다. 각 줄마다 기어 중심의 $x,ドル $y$좌표를 뜻하는 정수 $x_i,ドル $y_i$와 기어의 반지름을 뜻하는 정수 $r_i$이 공백으로 구분되어 주어진다. $(-1,円 000\le x_i,y_i\le 1,円 000$; 1ドル\le r_i\le 1,円 000)$

출력

차량 모듈이 정상적으로 동작하게 하기 위해 필요한 최소 벨트 길이를 출력한다. 절대/상대 오차는 10ドル^{-6}$까지 허용한다.

제한

힌트