Max and Min

题目描述

Two kittens, Max and Min, play with a pair of non-negative integers $x$ and $y$. As you can guess from their names, kitten Max loves to maximize and kitten Min loves to minimize. As part of this game Min wants to make sure that both numbers, $x$ and $y$ became negative at the same time, and kitten Max tries to prevent him from doing so.

Each kitten has a set of pairs of integers available to it. Kitten Max has $n$ pairs of non-negative integers $(a_i, b_i)$, and kitten Min has $m$ pairs of non-negative integers $(c_j, d_j)$. As kitten Max makes a move, it can take any available pair $(a_i, b_i)$ and add $a_i$ to $x$ and $b_i$ to $y$, and kitten Min can take any available pair $(c_j, d_j)$ and subtract $c_j$ from $x$ and $d_j$ from $y$. Each kitten can use each pair multiple times during distinct moves.

Max moves first. Kitten Min is winning if at some moment both numbers $a, b$ are negative simultaneously. Otherwise, the winner of the game is kitten Max. Determine which kitten wins if both of them play optimally.

题意概述

有两个人 Max 和 Min，初始时有两个数$x$和$y$。Max 有$n$个数对$(a_i, b_i)$，Min 有$m$个数对$(c_j, d_j)$。两个人轮流操作，Max 先手。Max 可以选择一个数对$(a_i, b_i)$，将$x$加上$a_i$、$y$加上$b_i$；Min 可以选择一个数对$(c_j, d_j)$，将$x$减去$c_j$、$y$减去$d_j$。若在某一时刻$x, y$同时为负，则 Min 获胜，否则 Max 获胜。求谁必胜。

数据范围：$1 \le n, m \le 10^5, \ 1 \le x, y, a_i, b_i, c_j, d_j \le 10^9$。

算法分析

对于两个向量$v_1, v_2$，我们用$(v_1, v_2)$表示$v_1 \cdot v_2$。

我们把所有数对看成从原点出发的向量。假设有一个新的向量$(a, b)$。若

$$
\begin{align}
&\exists (a, b), \ a, b \ge 0 \land a+b \gt 0, \\
&\exists (a_i, b_i), \ \forall (c_j, d_j), \ ((a_i, b_i), (a, b)) \ge ((c_j, d_j), (a, b))
\end{align}
$$

那么 Max 必胜。证明如下：

$\because$初始时$((x, y), (a, b))=ax+by \gt 0$

$((a_i-c_j, b_i-d_j), (a, b))=((a_i, b_i), (a, b))-((c_j, d_j), (a, b)) \ge 0$

$\therefore$在任意时刻$((x’, y’), (a, b)) \gt 0$

$\therefore x’, y’$不全为负数

由此得证。

若$\exists (c_{j_0}, d_{j_0}), (c_{j_1}, d_{j_1})$，点$(a_i, b_i)$严格在点$(c_{j_0}, d_{j_0})$、$(c_{j_1}, d_{j_1})$和原点所组成的三角形内部，那么根据上述证明，$(a_i, b_i)$对 Max 没有贡献。特别的，若

$$
\exists (c_j, d_j), \ (a_i, b_i) \parallel (c_j, d_j) \land |(a_i, b_i)| \lt |(c_j, d_j)|
$$

那么$(a_i, b_i)$也没有贡献。

算法已经很清晰了——对 Min 的向量求凸包，判断是否所有 Max 的向量都严格在凸包内部。假设 Min 的向量中$c_j$的最大值为$mx_c$，$d_j$的最大值为$mx_d$，凸包中还需加入三个点$(0, 0), (mx_c, 0), (0, mx_d)$。

具体实现时，可以将 Max 的向量拿来一起求凸包。若求出来的凸包上有 Max 的向量，则 Max 必胜，否则 Min 必胜。

代码

#include <vector>
#include <cstdio>
#include <algorithm>

#define int long long

typedef const int ci;

inline int max(ci &a, ci &b) {
  return a > b ? a : b;
}

static ci N = 100005;
int st[N << 1];
std :: vector <int> rec;
struct Point {
  int type, x, y;
  Point(ci &_x = 0, ci &_y = 0) : type(0), x(_x), y(_y) {}
  bool operator == (const Point &p) const {
    return type == p.type && x == p.x && y == p.y;
  }
  bool operator < (const Point &p) const {
    return x == p.x ? y < p.y : x < p.x;
  }
  Point operator - (const Point &p) const {
    return Point(x - p.x, y - p.y);
  }
  int operator * (const Point &p) const {
    return x * p.y - y * p.x;
  }
} p[N << 1];

signed main() {
  int n, m, tot, mxa = 0, mxb = 0; scanf("%lld%lld%*d%*d", &n, &m), tot = n + m + 3;
  for (int i = 0; i < n; ++ i) scanf("%lld%lld", &p[i].x, &p[i].y), p[i].type = 1;
  for (int i = n; i < n + m; ++ i) scanf("%lld%lld", &p[i].x, &p[i].y), p[i].type = 2, mxa = max(mxa, p[i].x), mxb = max(mxb, p[i].y);
  p[n + m] = Point(0, 0), p[n + m + 1] = Point(mxa, 0), p[n + m + 2] = Point(0, mxb), std :: sort(p, p + tot);
  for (int i = 0, j; i < tot; i = j) {
    j = i; int rec = 0;
    while (j < tot && p[i].x == p[j].x && p[i].y == p[j].y) ++ j;
    for (int k = i; k < j; ++ k) rec |= p[k].type;
    if (rec & 1) for (int k = i; k < j; ++ k) p[k].type = 1;
  }
  tot = std :: unique(p, p + tot) - p;
  int sz = 0;
  for (int i = 0; i < tot; ++ i) {
    while (sz > 1 && (p[st[sz - 1]] - p[st[sz - 2]]) * (p[i] - p[st[sz - 1]]) < 0) -- sz;
    st[sz ++] = i;
  }
  for (int i = 0; i < sz; ++ i) rec.push_back(st[i]); sz = 0;
  for (int i = tot - 1; ~ i; -- i) {
    while (sz > 1 && (p[st[sz - 1]] - p[st[sz - 2]]) * (p[i] - p[st[sz - 1]]) < 0) -- sz;
    st[sz ++] = i;
  }
  for (int i = 1; i < sz - 1; ++ i) rec.push_back(st[i]);
  for (int i = rec.size() - 1; ~ i; -- i) if (p[rec[i]].type == 1) return printf("Max\n"), 0;
  return printf("Min\n"), 0;
}