题目描述

凭借超光速引擎的研发，来自字节星的宇宙飞船开始殖民可观测宇宙中的其他星球。目前，总共有 $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} $$

4
-1 0
0 0
3 3
-1 1

7.001
6.655
13.71477
6.885

样例 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\%$。也就是这组子任务没有实现附加限制的测评要求。

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

using std::numbers::pi;
constexpr int K = 100;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    std::vector<int> x(n), y(n);

    for (int i = 0; i < n; i++) {
        std::cin >> x[i] >> y[i];
    }

    std::vector<double> a(n);

    std::vector<double> ans(n);

    std::vector<int> p(n);
    std::iota(p.begin(), p.end(), 0);

    for (int t = 0; t < K; t++) {
        double sin = std::sin(t * pi / K);
        double cos = std::cos(t * pi / K);

        for (int i = 0; i < n; i++) {
            a[i] = cos * x[i] + sin * y[i];
        }

        std::sort(p.begin(), p.end(),
        [&](int i, int j) {
            return a[i] < a[j];
        });

        double sum = 0;

        for (int i = 0; i < n; i++) {
            if (i) {
                sum += i * (a[p[i]] - a[p[i - 1]]);
            }

            ans[p[i]] += sum;
        }

        sum = 0;

        for (int i = n - 1; i >= 0; i--) {
            if (i < n - 1) {
                sum += (n - 1 - i) * (a[p[i + 1]] - a[p[i]]);
            }

            ans[p[i]] += sum;
        }
    }

    std::cout << std::fixed << std::setprecision(10);

    for (int i = 0; i < n; i++) {
        ans[i] *= pi / 2 / K;
        std::cout << ans[i] << "\n";
    }

    return 0;
}