Projection
给定 n 维空间中的点 x=(x1,…,xn),以及区域
$$S=\left\{\boldsymbol y\in\mathbb R^n:\sum_{i=1}^n y_i^2\le a,\quad |y_i|\le l_i\ (1\le i\le n)\right\}.$$
求 S 中距离 x 最近的点。也就是在这些约束下,最小化
i=1∑n(xi−yi)2.
区域包含边界,输入中的 a 是球半径的平方。
输入格式
第一行整数 T,1≤T≤3×104。每个用例包含三行:
- 两个整数 n,a,2≤n≤105,1≤a≤109。
- n 个整数 x1,…,xn,∣xi∣≤109。
- n 个整数 l1,…,ln,1≤li≤100。
所有用例的 n 之和不超过 105。
输出格式
对每个用例输出一行 n 个实数 y1,…,yn。
设标准答案的第 i 个坐标为 yi∗,输出必须对所有坐标满足
max(1,∣yi∗∣)∣yi−yi∗∣≤10−6.
样例
输入:
3
2 25
1 10
4 4
2 25
10 1
4 4
3 6
3 3 3
2 2 2
输出:
1.000000000000000 4.000000000000000
4.000000000000000 1.000000000000000
1.414213562373095 1.414213562373095 1.414213562373095