题解：P16537 [THUPC 2026 决赛] 星图重绘

· · 题解

题意简述

给定横、纵坐标均两两不同的 n 个点。选出尽可能多的三角形，要求各三角形内部两两不交，且每个三角形的三个顶点都在某个轴对齐矩形的边界上，输出最优方案。

解题思路

将一个三角形的三个顶点按横坐标排序，记为 a,b,c。左右两点一定在外接轴对齐矩形的边界上。中间点 b 也在边界上，当且仅当它的纵坐标大于另外两点，或者小于另外两点。

这个条件不仅充分，而且必要：任何包含三个点的轴对齐矩形都包含它们的最小外接矩形。若 b 的横、纵坐标都严格介于另外两点之间，那么它已经处于最小外接矩形的内部，更不可能落到其他可行矩形的边界上。

由此得到一个计数上界。若 b 是最高点，从 b 向下的竖直射线会进入三角形内部；若 b 是最低点，则向上的射线会进入内部。同一个点的同一方向不能用于两个三角形，否则该射线靠近顶点的一小段会同时处于两个三角形内部，违反要求。

因此，每个三角形必须使用一条独占的竖直射线，并且：

所求数量不超过这两类可用射线的总数。下面构造一组方案，恰好把它们全部用上。

先按纵坐标从小到大插入所有点，用有序集合维护已经插入的点，按横坐标排序。插入点 p 时，若它在集合中同时有左邻居 l 和右邻居 r，就输出三角形 (l,p,r)。

因为 l,r 都先于 p 插入，它们的纵坐标都小于 p。同时，p 的横坐标介于两者之间，因此三角形合法。存在左右邻居，恰好等价于原点集中左右两侧都有更低的点。所以这一遍会为每条可用的向下射线产生一个三角形。

这一遍产生的三角形内部两两不交。考虑把当前集合中的点按横坐标依次连接，形成一条折线。插入 p 后，原来的边 lr 被两条边 lp,pr 替换。由于 p 高于 l,r，新折线在这个区间严格高于原来的边，两条折线之间的区域恰好就是新三角形。

已有三角形都位于原折线下方，新三角形位于原折线上方，因此不会与已有三角形的内部相交。更新后，所有三角形仍位于新折线下方。若新点插入在横坐标最左端或最右端，仅扩展折线，不产生三角形，已有区域也不会受到影响。这个性质从空集合开始始终成立。

然后按纵坐标从大到小，再独立执行一次相同操作。此时新点低于左右邻居，新三角形位于旧折线下方；这一遍的所有三角形最终都位于折线上方，并且内部两两不交。它们恰好使用全部可用的向上射线。

两遍结束时的折线相同，都是将全部点按横坐标顺序连接。第一遍的三角形在最终折线下方，第二遍的三角形在最终折线上方。因此两遍之间也不会发生内部相交，折线上的边界重合则是允许的。

每条可用竖直射线恰好贡献一个三角形，构造数量达到上界，所以方案最优。

实现中保留原始编号 id，每次插入后用有序集合的前驱和后继取得左右邻居。solve 完成一遍构造，反转按纵坐标排序的数组后再次调用。每遍至多产生 n-2 个三角形，因此结果数组按 2n 的规模分配即可。

排序和两遍集合操作的总时间复杂度为 O(n\log n)，空间复杂度为 O(n)。

参考代码

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

const int N=200005;
const int M=400005;
struct node
{
    int x,y,id;
}a[N];
array<int,3> ans[M];
int cnt;
bool cmp(node a,node b){return a.y<b.y;}
void solve(int n)
{
    set<pair<int,int>> s;
    for(int i=1;i<=n;i++)
    {
        auto it=s.insert({a[i].x,a[i].id}).first;
        if(it==s.begin()||next(it)==s.end())continue;
        ans[cnt++]={prev(it)->second,a[i].id,next(it)->second};
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){cin>>a[i].x>>a[i].y;a[i].id=i;}
        sort(a+1,a+n+1,cmp);
        cnt=0;
        solve(n);
        reverse(a+1,a+n+1);
        solve(n);
        cout<<cnt<<'\n';
        for(int i=0;i<cnt;i++)cout<<ans[i][0]<<' '<<ans[i][1]<<' '<<ans[i][2]<<'\n';
    }
    return 0;
}