#P17516. [ECUSTPC 2026 Fall] 位距!?
[ECUSTPC 2026 Fall] 位距!?
题目描述
请在欧氏平面上构造一个 个点的点集,使得:
- 每个点的横坐标和纵坐标绝对值分别不超过 ;
- 每个点的横坐标和纵坐标分别乘上 是一个整数。
- 任意两点之间的距离不小于 ;
- 至少存在 $\left\lfloor \frac{1}{2}n\log_2 n - n \right\rfloor$ 个不同的无序点对距离在 之间。
输入格式
第一行输入一个整数 (),表示测试数据的数量。
每组测试数据输入一行一个整数 (),表示需要选定的点的数量。
保证所有测试数据的 。
输出格式
对于每组测试数据,输出 行,每行输出两个整数 (),表示第 个点的坐标实际为 $\left( \frac{X_i}{10^{13}}, \frac{Y_i}{10^{13}}\right)$。
你的输出将被视为正确,当且仅当它符合上述输出格式要求及题目描述中的四个条件。
如果有多个合法的答案,则你可以输出其中任意一个。
1
3
0 0
10000000000000 0
5000000000000 8660254038000
提示
样例 1 解释
对于第 1 组测试数据,实际点坐标为:
$$(x_1, y_1) = (0, 0), (x_2, y_2) = (1, 0), (x_3, y_3) = (0.5, 0.8660254038)$$前三个条件不难验证,对于第四个条件,有:
$$d_{12} = 1, d_{13} = d_{23} = 1.000000000013476527219909191607\ldots \approx 1 + 1.3476 \times 10^{-11}$$因此每个点对之间的距离都在 的误差范围内,这是符合第四个条件的。