AT1202Contest_k ± Beam

[problemUrl]: https://atcoder.jp/contests/DEGwer2023/tasks/1202Contest_k DEGwer さんは平面上の $ [-W,\ W]\ \times\ [-H,\ H] $ の土地を所有しており，ここで農業を営んでいます． 鳥獣被害に悩まされた DEGwer さんは，土地に侵入した動物を焼き払うビームを張り巡らせることにしました． 具体的には，土地内の格子点に $ + $ か $ - $ のいずれかの符号が付いた柱を立て，**符号の異なる柱同士**を結ぶ線分としてビームを張ります． ただし，ビーム同士が柱の無い点で交わると，ビームの持つエネルギーが共鳴して大変なことが起こるため，ビーム同士は柱の無い点を共有しないようにしなければなりません． DEGwer さんは，柱を立てる $ N $ 個の格子点 $ (X_i,\ Y_i)\ (i\ =\ 1,\ 2,\ \dots,\ N) $ を既に決めています． その中には土地の四隅すべてが含まれ，さらに柱を立てるどの $ 3 $ 点も同一直線上には存在しません． 各柱の符号とビームを張る柱のペアを適切に定めて，張るビームの数を最大にしてください．

N/A

N/A

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