きつねのしえるは,休暇でとある小さな村を訪れている.彼女が驚いたのは,その村の表札がもつ性質である.
村には N 個の家屋がある.ここでは簡単のため,村は 2 次元平面であるとし,家屋はこの平面上の点であると見なす. それぞれの家屋には表札が 1 個設けられており,その家の苗字を表していた.しえるは村の中を訪問するにつれて,この村の表札が次のような性質を持っていることに気付いた.
ここで,家屋同士の距離は,平面上のユークリッド距離によって計測するものとする.
しえるはこの村に表札が全部で何種類あるのかが気になったが,この村は意外に広いということに気付いたので,計算機を使ってこの答えを模索することにした.
入力は以下の形式で与えられる.
N R x1 y1 x2 y2 ... xN yN
N は家屋の個数である.R は家屋の配置の制約に関する値である. (xi, yi) は家屋 i の座標を表す.
村に存在する表札の種類の数を求めよ.
この問題の判定には,15 点分のテストケースのグループが設定されている. このグループに含まれるテストケースは上記の制約に加えて下記の制約も満たす.
5 3.000 1.000 0.000 0.000 0.000 -1.000 0.000 10.000 0.000 -10.000 0.000
3
家屋 1,2,3 と家屋 4 と家屋 5 で表札が異なる.全体で 3 つの表札が存在する.
12 1.234 0.500 0.000 -0.500 0.000 0.000 0.000 0.000 -0.500 55.500 55.000 -55.500 55.000 55.000 55.000 55.000 -55.500 99.500 99.000 -99.500 99.000 99.000 99.000 99.000 -99.500
7
5 99.999 0.000 0.000 49.999 0.001 0.000 0.000 -49.999 -0.001 0.000 0.000
1