题意
有数个大头钉在二维平面上，有四个人从不同的角度观察它们，重叠的点视为一个，是否可能有一个人观察到的大头钉数量远多余其他人？
让我们把大头钉的位置简化为二维坐标上的点。四个人观察的角度如下：
A从左往右观察。即所有 \(y\) 坐标相同的点是重叠的。B从左下往右上观察。即所有 \(x\) 坐标与 \(y\) 坐标相减的值相同的点是重叠的。C从下往上观察。即所有 \(x\) 坐标相同的点是重叠的。D从右下往左上观察。即所有 \(x\) 坐标与 \(y\) 坐标相加的值相同的点是重叠的。
令 A, B, C, D 观察到的大头针数量为 \(a, b, c, d\)，你需要构造一组大头针的排布，满足以下一些条件：
- \(d \geq 10 \times \max\{a, b, c\}\)
- 大头钉的数量不多于 \(10^5\) 个。
- 大头钉的坐标均为 \([0, 10^9]\) 内的整数。
- 不存在两个坐标相同的大头钉。
没有输入，直接输出一组解。
题解
设 \(N = 10\)，那么满足题目要求的点集一定可以划分为若干集合，其中每个集合内的点 \(y\) 坐标相同，且这些集合的平均大小不小于 \(N\)；类似的，其也可以划分为若干集合，其中每个集合内的点 \(x\) 坐标相同，且这些集合的平均大小不小于 \(N\)。
我们现在考虑观察者 A 和观察者 C，发现其只有横纵坐标上的限制，故可以取 \(N\) 条平行于横轴的直线和 \(N\) 条平行于纵轴的直线，取其交点集合。可以发现这样构造的点集一定符合上述集合划分要求。
下面考虑观察者 B，可以发现如果按 \(x\) 坐标与 \(y\) 坐标相减的值划分点集，那么点 \(\left(x, y\right)\) 和点 \(\left(x + d, y + d\right)\) 一定在同一集合中，所以取 \(N\) 个合适的 \(d\) 值，对于上述只考虑观察者 A 和观察者 C 所构造出的点集中的每个点 \(\left(x, y\right)\)，将点 \(\left(x + d, y + d\right)\) 也放入最终答案集合。可以发现现在构造出的点集满足观察者 A，B，C 观察到的点均为不少于 \(N\) 个点重叠在一起的形成的点。
考虑最大化观察者 D 观察到的点的数量，即最大化 \(x\) 坐标与 \(y\) 坐标相加的值的数量，随机取上文中的两组直线和 \(N\) 个 \(d\) 值即可，由于值域很大，所以很少会有冲突的情况。最终答案点的数量为 \(N^3\)，可以通过本题。
Code
#include <bits/stdc++.h>
typedef int valueType;
typedef std::vector<valueType> ValueVector;
void print(valueType x, valueType y) {
std::cout << x << ' ' << y << '\n';
}
typedef std::mt19937 Engine;
typedef std::uniform_int_distribution<valueType> Distribution;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
constexpr valueType N = 40, V = 5e8;
const unsigned int seed = (unsigned int) std::chrono::system_clock::now().time_since_epoch().count();
std::cout << N * N * N << '\n';
Engine engine(seed);
Distribution distribution(0, V);
ValueVector X(N), Y(N), D(N);
for (valueType i = 0; i < N; ++i) {
X[i] = distribution(engine);
Y[i] = distribution(engine);
D[i] = distribution(engine);
}
for (auto const &x: X)
for (auto const &y: Y)
for (auto const &d: D)
print(x + d, y + d);
std::cout << std::flush;
return 0;
}