Migrated from Lutece 2881 地毯

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

大兔子住在一个形状是凸多边形的房子内，他想在房子内铺三张地毯。三张地毯均是半径为 $r$ 的圆形，整个地毯必须位于房子内，不过地毯之间可以有重叠。如果三张地毯的圆心坐标分别是 $(x_1,y_1)$, $(x_2,y_2)$, $(x_3,y_3)$，那么第一张地毯的美丽度为 $w_1=x_1(y_2-y_3)$，第二张地毯的美丽度为 $w_2=x_2(y_3-y_1)$，第三张地毯的美丽度为 $w_3=x_3(y_1-y_2)$，三张地毯的总美丽度为 $|w_1+w_2+w_3|$。请问大兔子能得到的最大的总美丽度是多少。

Input

第一行包含一个整数 $T$ ($1 \le T \le 30$)，表示数据组数。

对于每组数据，第一行包含两个整数 $n$ 和 $r$ ($3 \le n \le 1000$, $0<r<1000$)，分别表示凸多边形的顶点数和地毯的半径。

接下来 $n$ 行每行两个整数 $x,y$ ($|x|,|y|\le50000$)，表示凸多边形的顶点坐标，按顺时针顺序给出。

输入保证一定有铺地毯的方案。

Output

对于每组数据，输出最大的总美丽度。请使用科学计数法的方式输出，保留七位有效数字（即 printf("%e\n", ans)）。

Samples

2
5 2
-2 0
-5 3
0 8
7 3
5 0
4 1
0 0
0 3
3 3
3 0

1.771543e+01
1.000000e+00

Resources

2022, 2023 UESTC ICPC Training for Geometry