！？starmap？！

Swirling · 2026-06-22 11:34:57 · 题解

不会做 [省选联考 2026] 星图 / starmap，所以来做这个题。

考虑和谐三角形的双射，即三点坐标在按照 x 坐标从大到小排序之后 y 坐标不单调，这是比较显然的。

那么我们考虑按 x 坐标从大到小的顺序依次加入节点。由于要求三角形之间不相交，所以我们与新加入的点组成合法三角形的店只会暴露在左侧。具体的，如下图标红的点。

我们称这些点为左侧点。不难发现这些左侧点在按照 y 轴从小到大排序后 x 坐标是单谷的，因为如果不是则两个谷至少会组成一个合法三角形。

考虑哪些左侧点会与新加入的点形成合法三角形。显然，在最优情况下，每个三角形组成所需的左侧点是相邻的。再通过一些简单的手玩可以发现合法的左侧点对是 y 坐标恰好包住新加入点 的左侧点对和 其中一端是波谷 的左侧点对。

这个信息可以轻松通过 set 维护。由于每个点至多被加入并删除一次，所以均摊下来时间复杂度 \mathcal{O}(n \log n)。

:::success[code]

细节有点多，但不是很难调。

#include <bits/stdc++.h>
#define int long long
#define pii std::pair< int, int >
const int N = 2e5 + 5;
int n; struct A { int x, y, i; } a[N]; 
signed main() {
    std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
    int T = 1; std::cin >> T; while (T--) {
        std::cin >> n; for (int i = 1; i <= n; ++i) std::cin >> a[i].x >> a[i].y, a[i].i = i;
        std::sort(a + 1, a + n + 1, [&](A x, A y) { return x.x < y.x; });  
        std::set< pii > S; std::vector< std::tuple< int, int, int > > ans;  // 左侧点集与答案
        S.insert({-1e9, n + 1}), S.insert({1e9, n + 1});
        for (int i = n; i; --i) {  // 按照 x 坐标倒序枚举
            if (S.size() <= 1) { S.insert({a[i].y, i}); continue; }
            auto R = S.upper_bound({a[i].y, 0}), L = std::prev(R);  // 恰好包住点 i 的左侧点对 [*L, *R]
            if (R->second != n + 1 && L->second != n + 1) ans.emplace_back(a[L->second].i, a[R->second].i, a[i].i);  // 单独加入 [*L, *R, i] 的答案
            if (L->second < R->second) while (L->second != n + 1 && std::prev(L)->second < L->second)  // 分讨 [*L, *R] 在波谷的哪一侧
                L = std::prev(L), R = std::prev(R), ans.emplace_back(a[L->second].i, a[R->second].i, a[i].i), R = S.erase(R);
            else while (std::next(R)->second != n + 1 && std::next(R)->second < R->second)
                R = std::next(R), L = std::next(L), ans.emplace_back(a[L->second].i, a[R->second].i, a[i].i), L = std::prev(S.erase(L));
            S.insert({a[i].y, i});  // 由于 i 的 x 坐标最小，所以结束后它一定是左侧点
        } std::cout << ans.size() << "\n";
        for (auto [x, y, z] : ans) std::cout << x << " " << y << " " << z << "\n";
    }
    return 0;
}

:::