AT1202Contest_k ± Beam

DEGwer 先生拥有一片平面上的土地，范围为 $ [-W,\ W]\ \times\ [-H,\ H] $，他在这里从事农业。由于受到鸟兽的侵害，DEGwer 先生决定在土地上建立一些柱子，用来驱赶入侵的动物。具体来说，他会在土地的格点上建立柱子，每个柱子上会标有 $+$ 或 $-$ 的符号，并且会用线段将不同符号的柱子连接起来，形成光束。然而，如果两束光束在柱子以外的点相交，那么它们的能量会共振，这样会产生很大的麻烦。因此，光束之间不能共享柱子以外的点。 DEGwer 先生已经确定了 $ N $ 个格点 $(X_i,\ Y_i)\ (i\ =\ 1,\ 2,\ \dots,\ N)$ 上的柱子位置。这些柱子包括土地的四个角，而且没有三个柱子共线。请合理选择柱子的符号和连接柱子的方式，使得可以张开的光束数量最多。

输入包含一行，包括以下内容： > $ W\ H $ $ N $ $ X_1\ Y_1 $ $ X_2\ Y_2 $ $ \cdots $ $ X_N\ Y_N $

输出包含以下内容： > $ S $ $ M $ $ P_1\ Q_1 $ $ P_2\ Q_2 $ $ \cdots $ $ P_M\ Q_M $ - $ S $ 是一个长度为 $ N $ 的字符串，只包含字符 $+$ 或 $-$，表示柱子的符号。第 $ i $ 个字符 $ S_i $ 表示柱子 $ i $ 的符号。 - $ M $ 是光束的最大数量，是一个整数。 - 对于 $ i\ =\ 1,\ 2,\ \dots,\ M $，$(P_i,\ Q_i)$ 表示柱子 $ P_i $ 和柱子 $ Q_i $ 之间会有一束光束。需要满足 $ S_{P_i}\ \neq\ S_{Q_i} $。 - 当 $ i\ \neq\ j $ 时，连接柱子 $(X_{P_i},\ Y_{P_i}) $ 和 $(X_{Q_i},\ Y_{Q_i}) $ 的线段和连接柱子 $(X_{P_j},\ Y_{P_j}) $ 和 $(X_{Q_j},\ Y_{Q_j}) $ 的线段除了端点以外没有公共点。 ### 约束 - $ 1\ \le\ W\ \le\ 10^9 $ - $ 1\ \le\ H\ \le\ 10^9 $ - $ 4\ \le\ N\ \le\ 10^5 $ - $ -W\ \le\ X_i\ \le\ W\ (1\ \leq\ i\ \leq\ N) $ - $ -H\ \le\ Y_i\ \le\ H\ (1\ \leq\ i\ \leq\ N) $ - 对于柱子位置 $(X_i,\ Y_i)$，不会存在 $ i $ 和 $ j $ 使得 $(X_i,\ Y_i) = (X_j,\ Y_j)$ - 存在某个 $ i $，使得 $(X_i,\ Y_i) = (\pm\ W,\ \pm\ H)$（符号可以是任意正负） - 对于任意四个不同的 $ i,\ j,\ k,\ l $，柱子位置 $(X_i,\ Y_i),\ (X_j,\ Y_j),\ (X_k,\ Y_k),\ (X_l,\ Y_l)$ 不共线。 Translate By [@XYQ_102](https://www.luogu.com.cn/user/712337)

### 制約 - $ 1\ \le\ W\ \le\ 10^9 $ - $ 1\ \le\ H\ \le\ 10^9 $ - $ 4\ \le\ N\ \le\ 10^5 $ - $ -W\ \le\ X_i\ \le\ W\ (1\ \leq\ i\ \leq\ N) $ - $ -H\ \le\ Y_i\ \le\ H\ (1\ \leq\ i\ \leq\ N) $ - $ (X_i,\ Y_i)\ \neq\ (X_j,\ Y_j)\ (i\ \neq\ j) $ - $ (X_i,\ Y_i)\ =\ (\pm\ W,\ \pm\ H) $（複号任意）であるような $ i $ が存在する． - $ i\ \neq\ j\ \neq\ k\ \neq\ i $ のとき，$ (X_i,\ Y_i),\ (X_j,\ Y_j),\ (X_k,\ Y_k) $ は同一直線上にない． ### Sample Explanation 1 DEGwer さんの所有する土地は $ [-1,\ 1]\ \times\ [-1,\ 1] $ であり，その四隅のみに柱を立てます． 柱に（反）時計回りに交互に異なる符号を割り当てることで，隣り合う柱同士の間すべてにビームを張ることができ，これが最大です． ### Sample Explanation 2 DEGwer さんの所有する土地は $ [-1,\ 1]\ \times\ [-2,\ 2] $ であり，その四隅と格子点 $ (0,\ 1) $ に柱を立てます． 四隅の柱に（反）時計回りに交互に異なる符号を割り当て，$ (0,\ 1) $ の柱に任意の符号を割り当てることで，出力例のように $ 6 $ 本のビームを張ることができます． また，$ 7 $ 本以上のビームを張れないことが証明できるので，これが最大であり答えの一例となります．