G - 道とN個のAtCoder社
Editorial
/
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