Nearest Point

题号：NC232892
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

Nearest point is a classical problem in computational geometry. Given a set $S$ of $n$ points $p_1, . . . , p_n, p_j$ is the nearest point of pi if $(1) j \neq i$ , and $(2)$ for any other point $p_k (k\not\in{i, j}), dis(p_i , p_j ) ≤ dis$ $(p_i , p_k)$ , where $dis$ $(p_1, p_2)$ is defined as $\sqrt{(p_1.x − p_2.x)^2 + (p_1.y − p_2.y)^2}$ in a $2-D$ space.

Calculating the neatest point is known to be difficult. Therefore, there are many heuristic methods proposed. The following describes one of these algorithms:

• Step1: A random angle $α$ is uniformly selected from range $[−π, π)$ .

• Step2: All points in $S$ are rotated $α$ counterclockwise centered on the origin $(0, 0)$ .

• Step3: For each point $p_i$ , the algorithm takes the point that is closest to $p_i$ on the $x-coordinate, i.e$ ., the point $p_j (i \neq j)$ that minimizes $|p_i .x − p_j .x|$ . If there are multiple such points, the point with the smallest index will be selected.

For example, suppose there are three points $p_1 = (1, 1)$ , $p_2 = (3, 3)$ , and $p_3 = (0, 2)$ in set $S$ .

1. When $α$ is selected as 0, the coordinates of these three points after the rotation are $(1, 1),(3, 3),(0, 2)$ , respectively, and thus the nearest points to $p_1, p_2, p_3$ found by the algorithm are $p_3, p_1, p_1$ , respectively.

2. When $α$ is selected as $\frac{π}4$ , the coordinates of these three points after the rotation are $(0, \sqrt2),(0, 3 \sqrt 2),(− \sqrt 2, \sqrt 2)$ , and thus the nearest points are $p_2, p_1, p_1$ , respectively.

Now, given the $n$ points $p_1, . . . , p_n$ in $S$ , your task is to output an $n × n$ matrix $w$ , where $w_{i,j}$ represents the probability for the algorithm to take $p_j$ as the nearest point of $p_i$ .

输入描述:

The first line contains a single integer , the number of points in S.
 Then  lines follow, each line contains two integers  and  . 
The input guarantees that each given point is different from the other

输出描述:

Output  lines, each with  float numbers. The  number in the  line represents the probability for  to be returned as the nearest point by the algorithm. 
Note that for each , the  number in the  line is always 0. 
Your result is judged as correct if for each probability, either the relative error or the absolute error comparing with the standard output is at most  . 
Note: The space at the end of a line will be ignored.

示例1

输入

复制

输出

复制

0.00000000 0.29516721 0.70483279
0.57797916 0.00000000 0.42202084
0.75000004 0.24999996 0.00000000

示例2

输入

复制

输出

复制

0.00000000 1.00000000 0.00000000
1.00000000 0.00000000 0.00000000
0.00000000 1.00000000 0.00000000

示例3

输入

复制

输出

复制

0.00000000 0.00909209 0.00396988 0.98570675 0.00123125
0.87050435 0.00000000 0.05126782 0.05576056 0.02246725
0.01389151 0.27660743 0.00000000 0.27929864 0.43020240
0.98698866 0.00782892 0.00395991 0.00000000 0.00122250
0.00558540 0.30017070 0.59898322 0.09526066 0.00000000

说明

810975，萌新怎么听不懂！922768，萌新怎么不知道？