这是一个关于 计算几何 中 闵可夫斯基和 (Minkowski Sum) 的经典应用题。

题目分析

1. 问题转化

题目给定两个点集 $A$（部落1）和 $B$（部落2）。部落 $B$ 的所有点移动向量 $\vec{d} = (dx, dy)$ 后，变为 $B' = \{b + \vec{d} \mid b \in B\}$。 如果在移动后，两个部落的凸包（Convex Hull）有交集，则判定为发生冲突。

两个凸包 $P_A$ 和 $P_{B'}$ 有交集，等价于存在点 $p$ 同时属于两个凸包：

即存在 $a \in P_A$ 和 $b \in P_B$，使得：

移项得：

这意味着，如果向量 $\vec{d}$ 可以表示为 $A$ 中的一个点减去 $B$ 中的一个点，那么就存在冲突。 令集合 $S = \{a - b \mid a \in P_A, b \in P_B\}$。 根据闵可夫斯基和的定义，$S$ 实际上就是 $P_A$ 与 $-P_B$（即 $P_B$ 关于原点对称后的图形）的闵可夫斯基和：

结论：我们要判断 $\vec{d}$ 是否会导致冲突，只需要判断点 $\vec{d}$ 是否在 凸多边形 $S$ 的内部（或边界上）。

2. 闵可夫斯基和的性质与构造

• 凸性：两个凸多边形的闵可夫斯基和仍然是凸多边形。
• 顶点与边：新凸多边形的边是由原两个多边形的边，按照极角排序后首尾相接构成的。
• 构造算法：
  1. 求出点集 $A$ 的凸包 $P_A$。
  2. 求出点集 $B$ 的凸包 $P_B$，并将所有坐标取反得到 $-P_B$（或者在计算时直接将 $B$ 的点取反求凸包）。
  3. 将 $P_A$ 和 $-P_B$ 的边提取出来。
  4. 将所有边按照极角大小进行归并排序。
  5. 从一个起始点（通常是 $P_A$ 的最低点加上 $-P_B$ 的最低点）开始，依次加上排序后的边向量，即可得到 $S$ 的所有顶点。

3. 询问处理

构造出凸多边形 $S$ 后，对于每个询问 $\vec{d}$，问题转化为 判定点是否在凸多边形内。 这可以通过二分查找在 $O(\log K)$ 的时间内完成（$K$ 为 $S$ 的顶点数，$K \le N + M$）。

代码详解

这份代码使用了非常规范的计算几何模板。以下是核心步骤的解析：

1. 基础几何模板

代码前半部分定义了 Point 和 Line 结构体，以及常用的向量运算：叉积 (cross)、点积 (dot)、点在直线左侧判定 (point_on_line_left) 等。这是解决几何问题的基石。

2. 求凸包 (convex_hull)

函数 convex_hull 使用了 Monotone Chain (单调链) 算法。

• 先对点进行排序（x坐标优先，y坐标次之）。
• 分别构建下凸壳 (l) 和上凸壳 (h)。
• 最终合并得到逆时针顺序的凸包顶点。

3. 构造闵可夫斯基和 (核心逻辑 solve 函数)

• 输入处理：

  std::vector<Point<int>> a(n);
  // ... 输入 a ...
  std::vector<Point<int>> b(m);
  for (int i = 0; i < m; i++) {
      std::cin >> b[i].x >> b[i].y;
      b[i] *= -1; // 关键：将 B 的坐标取反，即求 A + (-B)
  }
  

  这里直接将 $B$ 的坐标取反，实现了将“差”转化为“和”的处理。

• 求凸包： ha = convex_hull(a), hb = convex_hull(b)。

• 提取并合并边：

  // 提取边向量
  for (int i = 0; i < int(ha.size()); i++) edges.push_back(ha[(i + 1) % ha.size()] - ha[i]);
  for (int i = 0; i < int(hb.size()); i++) edges.push_back(hb[(i + 1) % hb.size()] - hb[i]);
  
  // 极角排序 (归并)
  std::ranges::inplace_merge(..., [&](Point<int> p, Point<int> q) -> bool {
      // 使用叉积和象限判断进行极角比较
      // ...
  });
  

  这里将两个凸包的边向量放在一起，按照角度进行排序。由于输入的凸包边本身就是有序的，使用 inplace_merge 可以高效地（线性时间）完成归并。

• 生成新多边形：

  std::vector hull = {ha[0] + hb[0]}; // 起点为两个凸包起点的和
  for (auto e : edges ...) {
      hull.push_back(hull.back() + e); // 依次累加边向量
  }
  

  最终得到的 hull 就是 $P_A$ 和 $-P_B$ 的闵可夫斯基和。

4. 处理询问 (点在凸多边形内判定)

对于每个询问 $\vec{d}$：

1. 特判：先检查是否在 $S$ 的第一条边对应的线段上。
2. 二分查找：

   int i = std::ranges::partition_point(hull | std::views::drop(1), [&](Point<int> p) -> bool {
       return !point_on_line_left<i64>(d, {p, hull[0]});
   }) - hull.begin();
   

   这里利用凸多边形的性质，以 hull[0] 为极点，二分找到点 $\vec{d}$ 所在的角区域（扇形区域）。
3. 最终判定： 判断 $\vec{d}$ 是否在这个扇形区域对应的外侧边的内侧（或边界上）。 !point_on_line_left<i64>(d, {hull[i], hull[i - 1]}) 用于判定点是否在边的右侧（因为代码中凸包是逆时针的，如果在左侧则是外部，右侧或共线则是内部）。注意代码逻辑最后的输出是 1 表示冲突（在内部），0 表示不冲突。

复杂度分析

• 求凸包: $O(N \log N + M \log M)$。
• 闵可夫斯基和: 边的归并排序是线性的（因为原凸包边已有序），耗时 $O(N + M)$。
• 查询: 共有 $Q$ 次查询，每次二分耗时 $O(\log (N+M))$。
• 总时间复杂度: $O(N \log N + M \log M + Q \log (N+M))$。

鉴于数据范围 $N, M, Q \le 10^5$，这个复杂度完全足以通过题目。