用于关联式容器的透明比较器技巧

日期:
标签: cpp trick

为什么不写到 C++ 技巧 里,单纯只是想水一份博客。

最近模拟赛考到了 [Ynoi2012] WC2016 充满了失望,题意大概是问有哪些圆在一个凸包内。大概思路是将圆按照半径排序,然后将凸包向内“收缩”,判断圆心是否在凸包内。难点就在于这个“收缩”:

convex hull

凸包上的顶点 A 和 B 分别会沿着角平分线 AE 和 BE 向内收缩,这个收缩的过程可以用一个线性的函数描述,可以令 表示收缩了 t 距离后顶点 A 应该在的位置。显然,如果收缩到了 E 这个位置,那么就应该将 A、B 两点删除,再加入一个新的点 F,这就需要支持在凸包上插入和删除,同时还需要支持二分,因为我们还要判断圆心是否在凸包上。插入删除这个工作用 set 很好搞定,但是如果我们要查询一个圆 是否在凸包内,就需要二分最靠后的的 (这里的小于都是先比较 x 再比较 y),直接 lower_bound 一个点是做不到的。

为了解决这个问题,我们需要写一个透明比较器。透明比较器就是有 is_transparent 类型的比较器,如果关联式容器检测到比较器有 is_transparent,那么在比较的时候就不会将比较的对象强转成 key_type,而会原封不动的传给比较器。一个典型的例子是 std::less<void>,它可以比较任意类型,但是无须类型转换。对于这道题,我们在 set 中存入各个点的收缩函数 ,对于两个收缩函数的比较,我们在两个函数的定义域的并中选一个点,计算出对应的点,进行比较,二分的时候,我们传入圆的圆心 和半径 ,按照上面说的东西比较即可。

比较器大概写成这样:

struct Compare
{
  using is_transparent = void;

  template <typename T, typename X>
  bool operator()(const std::pair<LinearFunc<T, X>, int> &a, const std::pair<LinearFunc<T, X>, int> &b) const
  {
    X x = std::max(a.first.s, b.first.s);
    return a.first.calc(x) < b.first.calc(x);
  }

  template <typename T, typename X>
  bool operator()(const std::pair<LinearFunc<T, X>, int> &a, const std::pair<T, X> &b) const
  {
    return a.first.calc(b.second) < b.first;
  }

  template <typename T, typename X>
  bool operator()(const std::pair<T, X> &a, const std::pair<LinearFunc<T, X>, int> &b) const
  {
    return a.first < b.first.calc(a.second);
  }
};

完整代码在 gist 上

一个要注意的点是,虽然透明比较器填什么都可以,但是一定要保证有单调性(要不然怎么二分)。

透明比较器还有许多有用的地方,比如说用 set 存了许多不交区间(比如珂朵莉树),想要找到包含某个点 x 的区间,一般做法是构造一个区间,左端点是 x,而右端点是什么就比较疑惑,而使用透明比较器就能轻松解决。再比如说用 set 存很多 vector,按照长度排序,想找到长度小于等于 k 的最大 vector 等。