AdditionalFile4838.zip

P9405 [POI 2020/2021 R3] 星间通信 / Komunikacja międzyplanetarn

题目背景

译自 XXVIII Olimpiada Informatyczna - III etap Komunikacja międzyplanetarn。

d2t1。

题目描述

二维平面上有 $n$ 个点。

对于每个点，算出它到其他所有点的欧氏距离之和。

相对误差不超过 $0.1\%$ 即可。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，每行两个整数 $x,y$，表示一个点的坐标。

输出格式

$n$ 行，每行一个实数，表示每个点的答案。

输入输出样例 #1

输入 #1

4
-1 0
0 0
3 3
-1 1

输出 #1

7.000000000000
6.656854249492
13.714776642119
6.886349517373

输入输出样例 #2

输入 #2

25
-2 -2
-2 -1
-2 0
-2 1
-2 2
-1 -2
-1 -1
-1 0
-1 1
-1 2
0 -2
0 -1
0 0
0 1
0 2
1 -2
1 -1
1 0
1 1
1 2
2 -2
2 -1
2 0
2 1
2 2

输出 #2

79.340412611230
68.023981606779
64.155694316737
68.023981606779
79.340412611230
68.023981606779
55.532407162959
51.265774235248
55.532407162959
68.023981606779
64.155694316737
51.265774235248
46.859106568475
51.265774235248
64.155694316737
68.023981606779
55.532407162958
51.265774235248
55.532407162959
68.023981606779
79.340412611230
68.023981606779
64.155694316737
68.023981606779
79.340412611230

输入输出样例 #3

输入 #3

见附件

输出 #3

见附件

说明/提示

对于所有数据，$2\leq n\leq 100000$，$-10^6\leq x,y\leq 10^6$。

子任务编号	附加限制	分数
1	$n\leq 1000$	4
2	所有点共线	16
3	点的坐标随机，相对误差不超过 $2\%$ 即可	20
4		60

#4838. 「POI 2020/2021 R3」Komunikacja międzyplanetarna

标签: 传统 | 时间限制: 15000 ms | 内存限制: 256 MiB |

题目描述

题目译自 XXVIII Olimpiada Informatyczna – III etap Komunikacja międzyplanetarna

凭借超光速引擎的研发，来自字节星的宇宙飞船开始殖民可观测宇宙中的其他星球。目前，总共有 $n$ 个星球被殖民。为了实现高效的通信，需要在每颗星球的轨道上放置一颗配备通信发射器的卫星。

每颗星球在宇宙中的位置可以用二维坐标 $(x, y)$ 表示（因此可以将宇宙建模为一个平面）。在两颗坐标分别为 $\left(x_{1}, y_{1}\right)$ 和 $\left(x_{2}, y_{2}\right)$ 的星球之间进行超光速通信所需的发射器功率，等于它们之间的距离，即 $\sqrt{\left(x_{1}-x_{2}\right)^{2}+\left(y_{1}-y_{2}\right)^{2}}$。每颗卫星上的发射器功率必须能够同时与所有其他星球通信，因此功率应等于该卫星与所有其他星球距离之和。

字节星政府希望了解每颗卫星所需的确切发射器功率，而你的任务就是计算这些值。由于这些数据仅用于估算卫星的成本，不需要非常精确，只要每个计算出的功率与实际值误差不超过 $0.1\%$（千分之一）即可。

输入格式

输入的第一行包含一个整数 $n$ $(2 \leq n \leq 100000)$，表示被殖民的星球数量。接下来的 $n$ 行描述每颗星球的位置，第 $i$ 行包含两个整数 $x, y$ $(-10^{6} \leq x, y \leq 10^{6})$，表示第 $i$ 颗星球的坐标。

你可以假设没有两颗星球位于同一位置。

输出格式

输出应包含正好 $n$ 行。设 $s_{i}$ 为第 $i$ 颗星球到所有其他星球的距离之和。在输出的第 $i$ 行，你需要输出一个实数 $s_{i}^{\prime}$，使用小数点格式（而不是科学计数法）。如果对于每个 $i$，输出值满足以下条件，结果将被认为是正确的：

$$\left|s_{i}-s_{i}^{\prime}\right| \leq \frac{s_{i}}{1000}$$

样例 1

输入

4
-1 0
0 0
3 3
-1 1

输出

7.001
6.655
13.71477
6.885

各星球到其他星球的精确距离之和（保留三位小数）分别为：
$7, 1+4\sqrt{2} \approx 6.657, 5+4\sqrt{2}+2\sqrt{5} \approx 13.715, 1+\sqrt{2}+2\sqrt{5} \approx 6.886$。

样例 2

见附加文件下 [kom1.in](file:kom1.in) 和 [kom1.out](file:kom1.out)。

该样例满足 $n=25$，星球坐标为 $(i, j)$，其中 $-2 \leq i, j \leq 2$；

样例 3

见附加文件下 [kom2.in](file:kom2.in) 和 [kom2.out](file:kom2.out)。

该样例满足 $n=100000$，星球坐标为 $(2i, i)$，其中 $0 \leq i < n$。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	附加限制	分值
$1$	$n \leq 1000$	$4$
$2$	所有星球位于同一直线上	$16$
$3$	星球位置从允许范围内均匀随机生成， 答案误差在 $2\%$（百分之二）内即可	$20$
$4$	无附加限制	$60$

注：由于 LibreOJ 实现限制，子任务 $3$ 中答案误差的要求仍为 $0.1\%$。也就是这组子任务没有实现附加限制的测评要求。