SP418 NECKLACE - Necklace

在平面上有 **N** 个点，每个点的坐标为 (**x $_{i}$**, **y $_{i}$**)。我们想要构造一个包含 **N** 个图形的集合，我们称这个集合为「项链」。为了满足项链的条件，需要满足以下规则： - 每个图形 **#i** 表示一个以点 (**x $_{i}$**, **y $_{i}$**) 为圆心，半径为 **r $_{i}$** 的圆，所有点 (**x**, **y**) 满足 (**x** - **x $_{i}$**)$^2$ + (**y** - **y $_{i}$**)$^2$ ≤ **r $_{i}$**$^2$。 - 图形 **#i** 必须与图形 **#(i+1)** 相交（1 ≤ **i** < **N**）。 - 图形 **#1** 必须与图形 **#N** 相交。 - 其余任意两图形之间都不能相交。 编写程序，给定点的坐标后，构造这样一个项链。

第一行输入一个整数 **t**，表示测试用例的个数 (1 ≤ **t** ≤ 45)。接下来是 **t** 组测试用例。 每个测试用例的第一行是一个整数 **N** (2 ≤ **N** ≤ 100)，后接 **N** 行，每行包含两个实数 **x $_{i}$**, **y $_{i}$** (-1000 ≤ **x $_{i}$**, **y $_{i}$** ≤ 1000)，以空格分隔。保证对于每个用例，至少存在一种满足条件的项链。

对于每个测试用例，输出 **N** 行，每行一个实数 **r $_{i}$**，表示相应图形的半径 (0 ≤ **r $_{i}$** < 10000)。为了避免精度问题，请使用下述规则： - 当 **r $_{i}$** + **r $_{j}$** ≤ **d $_{ij}$** - 10$^{-5}$ 时，表示图形 **#i** 和 **#j** 一定不相交。 - 当 **d $_{ij}$** + 10$^{-5}$ ≤ **r $_{i}$** + **r $_{j}$** 时，表示图形 **#i** 和 **#j** 一定相交。 - 对于 **d $_{ij}$** - 10$^{-5}$ < **r $_{i}$** + **r $_{j}$** < **d $_{ij}$** + 10$^{-5}$ 的情况，将按照有利于参赛者的方向判定。 - 其中 **d $_{ij}$** 表示两个图形圆心之间的距离，等于 $\sqrt{(\textbf{x} _\textbf{i} - \textbf{x} _\textbf{j}) ^2 + (\textbf{y} _\textbf{i} - \textbf{y} _\textbf{j}) ^2}$。 **本翻译由 AI 自动生成**