xy平面上に、 $1$ から $N$ の番号のついた $N$ 個の点が与えられます。
点のペアが以下の条件を満たすとき、それらの点は互いに接続すると定義します。
2 点が接続するとき、その 2 点間を線分で結ぶことにします。 この線分を「接続線」と呼ぶことにします。
点を頂点、接続線を辺とするグラフを考えたとき、ある 2 点が連結であるならば、その 2 点は互いに到達可能であると呼びます。
以下の操作をちょうど一度行って、点 $1$ と点 $N$ が互いに到達可能である状態にしたいです。
これは達成可能ですか？ 達成可能であるかを判定し、達成可能であれば追加する必要のある点の数の最小値を求めて下さい。
1行目に、点の数 $N$ が与えられる。 続く $N$ 行に、それぞれの点の座標 $x_i, y_i$ が与えられる。
$N$
$x_1$ $y_1$
$\hspace{11pt} \vdots$
$x_N$ $y_N$
問題の解を1行に出力せよ。
問題の内容が達成可能でない場合は、 -1 を1行に出力せよ。
5 1 2 2 1 2 5 5 2 10 4
2
点を追加する前は、点 $1, 4$ のペアと、点 $2, 3$ のペアが互いに到達可能な状態です。 座標 $(2, 2)$ と $(2, 4)$ に点を置くことで点 $1$ と点 $5$ が互いに到達可能になります。
4 10 0 10 20 0 10 20 10
1
接続線が交差していても、それぞれの接続線に繋がっている点同士が連結であるとは限りません。 この場合、交差した部分に点を追加することで点 $1$ と点 $4$ が互いに到達可能になります。
5 10 10 10 50 50 30 100 30 40 100
-1
点を追加する操作は一度だけ行われます。 操作の結果現れた接続線上に、新たに点を追加することは出来ないことに注意して下さい。