题目描述

给定平面上的 $n$ 个点。其中一些点是白色的，一些点是黑色的。没有两个点重合，也没有三个点共线。

你需要移动其中一个白点，移动距离不超过 $r$，使得操作之后所有点形成的凸包面积最大。

输入格式

每个测试包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例数量。

接下来描述每个测试用例。

每个测试用例第一行包含两个整数 $n,r$（$3 \le n \le 2000$，$1 \le r \le 10^9$），表示点的数量以及白点最大移动距离。

接下来 $n$ 行描述点。第 $i$ 行包含三个整数 $x_i,y_i,c_i$（$-10^9 \le x_i,y_i \le 10^9$，$1 \le c_i \le 2$），表示第 $i$ 个点的坐标和颜色。$c_i=1$ 表示白点，$c_i=2$ 表示黑点。

保证每个测试中所有测试用例的 $n$ 之和不超过 $2000$。

输出格式

对每个测试用例，单独输出一行，表示如果可以移动任意一个白点且移动距离不超过 $r$，操作之后所有点凸包面积的最大值。

若你的答案的绝对误差或相对误差不超过 $10^{-6}$，则认为正确。形式化地说，设你的答案为 $a$，评测答案为 $b$，当且仅当

时，答案被接受。

样例

样例输入 1

1
3 1
0 0 1
1 0 1
0 1 1

样例输出 1

1.20710678118655

样例输入 2

1
9 6
2 10 2
5 7 2
9 8 1
6 4 2
4 9 2
2 1 2
9 7 2
5 9 2
3 8 2

样例输出 2

59.34731931759172

样例输入 3

1
9 1
8 7 1
1 9 1
3 9 1
4 2 1
7 4 1
10 5 1
3 7 1
4 4 1
7 6 1

样例输出 3

37.42442890089805

样例解释

原题给出了三个样例的示意图。图中虚线表示新凸包的边，实线表示旧凸包的边以及新旧凸包共有的边，蓝色箭头表示白点的最优移动方向。

【图片占位】此处应插入原题中的样例 1、样例 2、样例 3 几何示意图。

计分方式

测试数据包含九个测试组。只有当某组所有测试点以及该组要求的若干前置组均通过时，才能获得该组分数。注意，某些测试组不一定要求通过样例测试。离线测试表示该组测试结果会在比赛结束后才可见。

令 $\sum n$ 表示该测试中所有测试用例的 $n$ 之和。