G - 道とN個のAtCoder社

Time Limit: 2 sec / Memory Limit: 128 MB

問題文

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 点 ]

  • 追加の制約はない。

入力例1

4
0 0
1 1
0 1
1 0

出力例1

5

点{(1,2),(1,3),(2,3),(1,4),(2,4)}を結べば5本の道を条件を満たして作ることができる。

入力例2

4
0 0
1 2
2 0
1 1

出力例2

6

この場合、全ての辺を結ぶことができます。

問題文担当者:E869120