题解：CF2072E

题目分析

题目要求构造不超过 $500$ 个互不相同的整点，使得恰好有 $k$ 对点满足欧几里得距离等于曼哈顿距离。

关键观察是：设两个点的横纵坐标差为 $|dx|, |dy|$，则

两边平方后得到

因此必须有 $|dx||dy|=0$。也就是说，两个不同点满足条件，当且仅当它们在同一条水平线或同一条竖直线上。

从暴力到正解

如果直接一个点一个点尝试放置，并在每一步统计新增的合法点对，搜索空间非常大，不适合 $k \le 10^5$。

我们换一个角度：如果把 $m$ 个点放在同一条水平线上，并保证它们的横坐标互不相同，那么这组点内部会贡献

对合法点。于是问题变成：把 $k$ 拆成若干个三角数之和。

对当前剩余的 $k$，每次贪心选择最大的 $m$，满足 $\binom m2 \le k$，放一组大小为 $m$ 的点，然后令 $k$ 减去这组贡献。不同组使用不同的纵坐标，同时让所有点的横坐标全局互不相同，这样跨组之间既不同横线，也不同竖线，不会产生额外贡献。

在 $k \le 10^5$ 时，最大的单组大小不超过 $447$，贪心拆分需要的总点数不超过 $500$，满足题目限制。

正解思路

对每个测试用例：

1. 初始化空点集，当前横坐标 next_x=0，当前组的纵坐标 y=0。

2. 当 $k>0$ 时，二分找到最大的 $m$，使得 $\binom m2 \le k$。

3. 放置 $m$ 个点：

   $$(next\_x,y),(next\_x+1,y),\ldots,(next\_x+m-1,y)$$

4. 将 next_x 增加 $m$，将 $y$ 增加一个足够大的常数，进入下一组。

5. 输出所有点。

每一组只通过相同的纵坐标贡献点对，贡献值正好是 $\binom m2$。所有横坐标全局唯一，所以不同组之间不会因为横坐标相同而贡献点对。

复杂度分析

每次拆出一组三角数，用二分寻找组大小，复杂度为 $O(\log 500)$。输出点数不超过 $500$。

因此单个测试用例的时间复杂度为 $O(500)$ 以内，空间复杂度为 $O(500)$。

参考代码（C++14）

#include <bits/stdc++.h>
using namespace std;

long long tri(int x) {
    return 1LL * x * (x - 1) / 2;
}

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

    int T;
    cin >> T;
    while (T--) {
        long long k;
        cin >> k;

        vector<pair<long long, long long> > pts;
        long long next_x = 0;
        long long y = 0;

        while (k > 0) {
            // 找到当前能放下的最大组大小 m，使得 C(m, 2) <= k。
            int l = 2, r = 500, m = 2;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (tri(mid) <= k) {
                    m = mid;
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }

            // 同一组的点共享 y，贡献 C(m, 2) 对。
            // 所有点的 x 全局唯一，避免不同组之间额外产生合法点对。
            for (int i = 0; i < m; ++i) {
                pts.push_back(make_pair(next_x++, y));
            }
            k -= tri(m);
            y += 1000000;
        }

        // 输出构造出的点集。
        cout << pts.size() << '\n';
        for (size_t i = 0; i < pts.size(); ++i) {
            cout << pts[i].first << ' ' << pts[i].second << '\n';
        }
    }

    return 0;
}