信用卡凸包

平面上有 $n$ 张形状和大小完全相同的信用卡。每张信用卡都是长度为 $a$、宽度为 $b$ 的圆角矩形，四个角均为半径 $r$ 的四分之一圆弧。

第 $i$ 张信用卡的中心为 $(x_i,y_i)$，旋转角为 $\theta_i$。当 $\theta_i=0$ 时，信用卡长度为 $a$ 的方向平行于 $y$ 轴，宽度为 $b$ 的方向平行于 $x$ 轴。$\theta_i$ 表示信用卡在此基准方向上绕中心逆时针旋转的角度，单位为弧度。

求包含所有信用卡所占区域的最小凸集，即所有信用卡的凸包的周长。

输入格式

第一行输入一个整数 $n$，表示信用卡的数量。

第二行输入三个实数 $a$、$b$、$r$，分别表示每张信用卡的长度、宽度和圆角半径。

接下来 $n$ 行，每行输入三个实数 $x_i$、$y_i$、$\theta_i$，表示第 $i$ 张信用卡的中心坐标和旋转角。

输出格式

输出凸包的周长，四舍五入保留 $2$ 位小数。

样例输入

2
6.0 2.0 0.0
0.0 0.0 0.0
2.0 -2.0 1.5707963268

样例输出

21.66

样例解释

本样例中有 $2$ 张信用卡。若将 $1.5707963268$ 视为 $\pi/2$，则其凸包的周长为 $16+4\sqrt{2}$。

数据范围

• $1\le n\le 10^4$；
• $0<a,b\le 10^4$，$0\le 2r\le\min(a,b)$；
• $|x_i|,|y_i|\le 10^6$；
• $0\le\theta_i<2\pi$。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

2
6.0 2.0 0.0
0.0 0.0 0.0
2.0 -2.0 1.5707963268

输出

21.66