#P18828. [Croatian CPC2018] Hulja

[Croatian CPC2018] Hulja

[Croatian CPC2018] Hulja

题目描述

平面上有 nn 个两两没有公共点的圆盘。它们的凸包是包含所有圆盘的最小凸区域,其边界由直线段和圆弧交替构成。

求凸包边界上最长的一段圆弧的长度。

输入格式

第一行包含一个整数 nn(2≤n≤10002\le n\le1000)。

接下来 nn 行,第 jj 行包含三个整数 xj,yj,rjx_j,y_j,r_j(−500≤xj,yj≤500-500\le x_j,y_j\le500,1≤rj≤5001\le r_j\le500),表示第 jj 个圆盘的圆心坐标和半径。

保证任意两个圆盘没有公共点。

输出格式

输出一个实数,表示所求最长圆弧的长度。

答案与标准答案的绝对误差不超过 10−510^{-5} 即视为正确。

样例 1

输入

3
2 1 2
2 9 2
2 5 1

输出

6.28318530717958623200

样例 2

输入

5
5 27 1
20 5 3
10 20 7
22 17 3
8 12 1

输出

6.23456167767951541236

样例示意图

样例 1:

样例1

样例 2:

样例2