# 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.

## 算法分析

\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}

$\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, d_j), \; (a_i, b_i) \parallel (c_j, d_j) \land |(a_i, b_i)| \lt |(c_j, d_j)|$$

## 代码

#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;
}


418 I'm a teapot