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