AT1202Contest_k ± Beam

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

无

无

### 制約 - $ 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 $ 本以上のビームを張れないことが証明できるので，これが最大であり答えの一例となります．