题目描述
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;
}
