Migrated from Lutece 3058 随机旋转法

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

最近点对是计算几何中的经典问题。给定一个包含 $n$ 个点的集合 $S$： $\{p_1, \dots , p_n\}$， 距离某点 $p_i$ 最近的点 $p_j(j \neq i)$ 即为满足 $\forall k \neq i,j$，有 $dis(p_i,p_j) \leq dis(p_i,p_k)$ 成立的点。其中，在二维平面上，两点之间的距离 $dis(p_1,p_2) = \sqrt{(p_1.x-p_2.x)^2 + (p_1.y-p_2.y)^2}$。 为了解决这个问题，有人提出了一种随机旋转的方法。算法的流程如下：

1. 在 $[-\pi , \pi)$ 内随机选取一个角度 $\alpha$ 。
2. $S$ 中的每个点绕原点 $(0,0)$ 以角度 $\alpha$ 逆时针旋转。
3. 对每个点 $p_i$，取 $x$ 轴方向上离其最近的点，即使得 $|p_i.x-p_j.x|$ 最小的点 $p_j$。若有多个这样的点，就取点的序号 $j$ 最小的。

例如，假设 $S$ 中有三个点 $p_1=(1,1)$，$p_2=(3,3)$，$p_3=(0,2)$，则

• 若 $\alpha$ 为 $0$，则点 $p_1,p_2,p_3$ 旋转后的坐标分别为 $(1,1),(3,3),(0,2)$，距离其最近的点分别为 $p_3,p_1,p_1$。
• 若 $\alpha$ 为 $\frac{\pi}{4}$，则点 $p_1,p_2,p_3$ 旋转后的坐标分别为 $(0,\sqrt{2}),(0,3\sqrt{2}),(-\sqrt{2},\sqrt{2})$，距离其最近的点分别为 $p_2,p_1,p_1$。

现在，给出 $S$ 中的 $n$ 个点，请你求出 $n\times n$ 的矩阵 $w$，其中 $w_{ij}$ 表示点 $p_j$ 被选为距离点 $p_i$ 最近的点的概率。

Input

第一行一个整数 $n$，表示点的个数。 接下来 $n$ 行，每行两个整数 $x_i,y_i$，表示一个点的坐标 $(x_i,y_i)$。点的序号 $i$ 由小到大。

Output

输出 $n$ 行，每行 $n$ 个浮点数（保留 $5$ 位小数）表示矩阵 $w$。其中，第 $i$ 行的第 $j$ 个数为 $w_{ij}$，即点 $p_j$ 被选作距离点 $p_i$ 最近的点的概率。 注意，$w_{ii}$ 均为 $0$。

Samples

3
1 1
3 3
0 2

0.00000 0.29517 0.70483
0.57798 0.00000 0.42202
0.75000 0.25000 0.00000

3
1 1
2 2
3 3

0.00000 1.00000 0.00000
1.00000 0.00000 0.00000
0.00000 1.00000 0.00000

5
8 10
9 75
810 9
7 5
810 975

0.00000 0.00909 0.00397 0.98571 0.00123
0.87050 0.00000 0.05127 0.05576 0.02247
0.01389 0.27661 0.00000 0.27930 0.43020
0.98699 0.00783 0.00396 0.00000 0.00122
0.00559 0.30017 0.59898 0.09526 0.00000

Constraints

$2\leq n \leq 50$， $|x_i|,|y_i| \leq 1000$

Resources

2023 UESTC ICPC Training for Geometry