AT_s8pc_2_g 道とN個のAtCoder社

[problemUrl]: https://atcoder.jp/contests/s8pc-2/tasks/s8pc_2_g $ Atcoder $運送会社には、$ N $個の工場が存在します。 217X年、この会社では、$ 1 $つだけ困っていることがあります。これは、会社と会社を結ぶ道が存在しないことです。 運送会社社長「これは大問題だ!!すぐにでも直さないとやばいぞ!!」 よって、今すぐ計画を立てることになりました。 この会社は、運送関連のことをやっているため、製品を地方から都市、都市から地方へ迅速に運ばなければなりません。そのため、会社専用の道を作ると多くの注文にも対応できます。 ただし、以下のような条件で道を作る必要があります。 - できるだけ運送トラックの制限速度を上げるために、道路は直線にする必要があります。 - 立体交差をすると大幅に費用が増えるので、道と道は工場以外で交差してはいけません。 - そのように全ての専用道路の制限速度を速くした上で、できるだけ目的の会社に速く速く運びたいので、 できるだけ道をつくります。 - 道は工場と工場の間をつなぐものとします。 ただ、会社は最適解を導き出す方法がわかりませんでした。 そこで、優秀なプログラマーであるあなたに、最適解を探してくれと会社から頼まれました。最大で道が何本建てられるか求めてください。 ただし、問題文中の条件は厳守するものとします。 注意:問題文中の217X年は、時空を超えた世界での時間とします。ここでの時間は今現在とみなしてよいでしょう。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ x_1 $ $ y_1 $ $ : $ $ : $ $ x_N $ $ y_N $ - $ 1 $ 行目には, 工場の総数 $ N $ が与えられる。 - $ 2 $ 行目から$ N+1 $行目にかけて、工場$ i $の座標$ (x_i,y_i) $が与えられます。

出力は以下の形式で標準出力に従うこと。 - 最大で何本の道を建てられるか、$ 1 $行で出力してください。

### 制約 - $ 1≦N≦2,000 $ - $ 0≦x_i,y_i≦1,000,000,000 $ - 3工場が一直線上に並ぶことはない。 ### 小課題 小課題 $ 1 $ \[ $ 14 $ 点 \] - $ 1≦N≦4 $ を満たす。 小課題 $ 2 $ \[ $ 50 $ 点 \] - $ 1≦N≦100 $を満たす。 小課題 $ 3 $ \[ $ 36 $ 点 \] - 追加の制約はない。 ### Sample Explanation 1 点{$ (1,2),(1,3),(2,3),(1,4),(2,4) $}を結べば$ 5 $本の道を条件を満たして作ることができる。 ### Sample Explanation 2 この場合、全ての辺を結ぶことができます。