P10821 [EC Final 2020] Rooks

庞教授与他的对手寿教授下棋。他们是游戏中仅有的两位玩家。棋盘非常大，可以看作是一个二维平面。庞教授放置了 $n_1$ 个车，寿教授放置了 $n_2$ 个车。每个车在棋盘上是一个具有整数坐标的点。如果一个车满足以下所有条件，则被另一个车「攻击」： - 它们由不同的玩家放置。 - 它们具有相同的 $x$ 坐标或 $y$ 坐标。 - 在它们之间的线段上没有其他车。 帮助庞教授和寿教授判断哪些车被攻击。

第一行包含两个整数 $n_1, n_2$ ($1\le n_1, n_2\le 200000$)，用一个空格分隔，表示庞教授放置的车的数量和寿教授放置的车的数量。 接下来的 $n_1$ 行中的第 $i$ 行 ($1\le i\le n_1$) 包含两个整数 $x, y$ ($-10^9\le x, y\le 10^9$)，用一个空格分隔，表示庞教授放置的第 $i$ 个车的位置 $(x, y)$。 接下来的 $n_2$ 行中的第 $i$ 行 ($1\le i\le n_2$) 包含两个整数 $x, y$ ($-10^9\le x, y\le 10^9$)，用一个空格分隔，表示寿教授放置的第 $i$ 个车的位置 $(x, y)$。 保证玩家放置的 $n_1+n_2$ 个车是不同的（即没有两个车可以有相同的位置）。

第一行输出一个长度为 $n_1$ 的字符串。如果庞教授放置的第 $i$ 个车被攻击，第 $i$ 个 ($1\le i\le n_1$) 字符应为 $1$，否则为 $0$。 第二行输出一个长度为 $n_2$ 的字符串。如果寿教授放置的第 $i$ 个车被攻击，第 $i$ 个 ($1\le i\le n_2$) 字符应为 $1$，否则为 $0$。

（由 ChatGPT 4o 翻译）