33OJ
登录 注册

#P17516. [ECUSTPC 2026 Fall] 位距!?

    ID: 20245 远端评测题 2000ms 1024MiB 尝试: 0 已通过: 0 显示难度省选/NOI− 上传者: 标签>Special Judge2026高校校赛

[ECUSTPC 2026 Fall] 位距!?

题目描述

请在欧氏平面上构造一个 nn 个点的点集,使得:

  • 每个点的横坐标和纵坐标绝对值分别不超过 10510^5;
  • 每个点的横坐标和纵坐标分别乘上 101310^{13} 是一个整数。
  • 任意两点之间的距离不小于 10−410^{-4};
  • 至少存在 $\left\lfloor \frac{1}{2}n\log_2 n - n \right\rfloor$ 个不同的无序点对距离在 [1−10−9,1+10−9][1 - 10^{-9}, 1 + 10^{-9}] 之间。

输入格式

第一行输入一个整数 TT (1≤T≤1001 \le T \le 100),表示测试数据的数量。

每组测试数据输入一行一个整数 nn (2≤n≤50002 \le n \le 5000),表示需要选定的点的数量。

保证所有测试数据的 ∑n≤5000\sum n \le 5000。

输出格式

对于每组测试数据,输出 nn 行,每行输出两个整数 Xi,YiX_i, Y_i (−1018≤Xi,Yi≤1018-10^{18} \le X_i, Y_i \le 10^{18}),表示第 ii 个点的坐标实际为 $\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}$$

因此每个点对之间的距离都在 11 的误差范围内,这是符合第四个条件的。