神秘图论建模题。

给定 组三维向量 。

保证对于任意 ，有 和 ，且 。

从前 个向量中选出 个 ，使得对于后 个向量的任意一个 ，可以选出非负的 个实数 ，满足 。

找到最小的 或报告不可能。

• 。

---

首先，由于限定了向量三维的和为 ，所以三维向量是假的，可以把第三维直接干掉，不过需要加上 的限制。

把 个点扔到二维平面上，容易发现，任选 个点，可以表出的向量为这 个点围成的凸包（含边界）。

考虑图论建模，在前 个点中，任选两个点 连成有向线段，若后 个点或在线段右侧，或在线段上，就在 之间连一个权值为 的有向边；否则连权值为 的有向边。

判断点是否在线段一侧可以使用叉积，也可以全判左侧，相当于将原图的边全部反向。

原问题被转化为最小环问题。

最简单的方式是跑一个 Floyd。

复杂度 ，注意代码中变量与本文中略有不同。

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

static constexpr double eps = 1e-12;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  size_t n, m;
  double tmp;
  cin >> n >> m;

  vector<pair<double, double>> origin(n);
  for (auto &[x, y] : origin)
    cin >> x >> y >> tmp;

  vector<pair<double, double>> target(m);
  for (auto &[x, y] : target)
    cin >> x >> y >> tmp;

  vector<vector<size_t>> F(n, vector<size_t>(n, numeric_limits<size_t>::max() >> 2));
  for (size_t i = 0; i < n; ++i) {
    const auto [x0, y0] = origin[i];
    for (size_t j = 0; j < n; ++j) {
      const auto [x1, y1] = origin[j];
      if ([&]() -> bool {
            for (size_t k = 0; k < m; ++k) {
              const auto [x2, y2] = target[k];
              const double cross = (x1 - x0) * (y2 - y0) - (y1 - y0) * (x2 - x0);
              bool inside = cross > eps;
              bool onsegment = abs(cross) < eps && (min(x0, x1) - eps <= x2 && x2 <= max(x0, x1) + eps);
              if (!inside && !onsegment)
                return false;
            }
            return true;
          }())
        F[i][j] = 1;
    }
  }
  for (size_t k = 0; k < n; ++k)
    for (size_t i = 0; i < n; ++i)
      for (size_t j = 0; j < n; ++j)
        if (F[i][j] > F[i][k] + F[k][j])
          F[i][j] = F[i][k] + F[k][j];
  size_t ans = numeric_limits<size_t>::max() >> 2;
  for (size_t i = 0; i < n; ++i)
    ans = min(ans, F[i][i]);
  if (ans == numeric_limits<size_t>::max() >> 2)
    cout << "-1\n";
  else
    cout << ans << '\n';
  return 0;
}