n 本の釘を平板上の座標 P1 (x1, y1), P2 (x2, y2), P3 (x3, y3),..., Pn (xn, yn) に1本ずつ打ち、輪ゴムの輪の中に全ての釘が入るように 1 本の輪ゴムで囲みます。このとき、輪ゴムが交差してはいけません。
釘の座標を読み込んで、上記のように釘を輪ゴムで囲んだときに輪ゴムに接していない釘の本数を出力するプログラムを作成してください。輪ゴムは充分に伸び縮みするものとします。同じ座標に 2 本以上の釘を打つことはないものとします。また、輪ゴムがかかった釘と釘の間は直線で結ばれるものとし、その直線上に 3 本以上の釘が並ぶことはないものとします。例えば、図 1 に示すような入力はありえません。図 2 に示すように輪ゴムがかかっていない釘が 1 直線上に並ぶことはありえます。
図1 | 図2 |
ただし、それぞれの座標値は -1000.0 以上1000.0 以下の実数です。また、n は 3 以上 100 以下の整数です。
複数のデータセットが与えられます。各データセットは以下のような形式です与えられます。
n x1, y1 x2, y2 ... ... xn, yn
n が 0 の時、入力の最後を示します。データセットの数は 50 を超えません。
データセットごとに、ゴムと接していない釘の本数を出力してください。 例えば、図 3 に示す4つの釘を表す入力があった場合、図 4 のように囲まれるので、輪ゴムに接していない釘の本数は 1 本です。
図3 | 図4 |
4 1.0,0.0 0.0,1.0 2.0,1.0 1.0,2.0 9 -509.94,892.63 567.62,639.99 -859.32,-64.84 -445.99,383.69 667.54,430.49 551.12,828.21 -940.2,-877.2 -361.62,-970 -125.42,-178.48 0
0 3
以下は2つめのサンプル入力に対する図です。