暴力做法：

合法即

$$(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2=r^2$$

也即

$$(x_1^2+y_1^2+z_1^2)-2x_1x_2-2y_1y_2-2z_1z_2=r^2-x_2^2-y_2^2-z_2^2 $$

也即

$$A_p+xB_p+yC_p+zD_p=S$$

就是给定 $(x,y,z,S)$，找到一个合法 $(A_p,B_p,C_p,D_p)$。

这样我们就可以 check 一个点是不是答案了。

暴力 check 是 $O(nm)$ 的，松一松能过。

---

似乎合理一点的做法：

考虑到这道题目保证数据随机，我们猜测 kdt 跑不满，直接 kdt 嗯上即可。由于数据随机，不妨采用直接插入的方法，而不必二进制分组。

对输入解码的部分，注意到函数是单调的，二分即可。由于 sinl 调用太多次太慢所以要先估一个粗界。

参考代码。