Village

Time Limit : 4 sec, Memory Limit : 131072 KB

G - 村

問題文

きつねのしえるは,休暇でとある小さな村を訪れている.彼女が驚いたのは,その村の表札がもつ性質である.

村には N 個の家屋がある.ここでは簡単のため,村は 2 次元平面であるとし,家屋はこの平面上の点であると見なす. それぞれの家屋には表札が 1 個設けられており,その家の苗字を表していた.しえるは村の中を訪問するにつれて,この村の表札が次のような性質を持っていることに気付いた.

  • ある実数 R が存在する.
  • もし 2 つの家屋の距離が R 以下であるなら,その 2 つの家屋は同じ表札を持つ.
  • もし 2 つの家屋の距離が 3R 以上であるなら,その 2 つの家屋は異なる表札を持つ.
  • 任意の 2 つの家屋の距離は R 以下であるか 3R 以上であるかのどちらかである.

ここで,家屋同士の距離は,平面上のユークリッド距離によって計測するものとする.

しえるはこの村に表札が全部で何種類あるのかが気になったが,この村は意外に広いということに気付いたので,計算機を使ってこの答えを模索することにした.

入力形式

入力は以下の形式で与えられる.

N R
x1 y1
x2 y2
...
xN yN

N は家屋の個数である.R は家屋の配置の制約に関する値である. (xi, yi) は家屋 i の座標を表す.

出力形式

村に存在する表札の種類の数を求めよ.

制約

  • 1 ≤ N ≤ 2 × 105
  • 1 ≤ R ≤ 103
  • |xi|, |yi| ≤ 106
  • N は整数である.R, xi, yi は実数で,小数第 3 位まで表される.
  • 任意の 1 ≤ i < j ≤ N に対して dij = √{(xi - xj)2 + (yi - yj)2} とおくとき,dij ≤ R3R ≤ dij のどちらかが満たされる.

この問題の判定には,15 点分のテストケースのグループが設定されている. このグループに含まれるテストケースは上記の制約に加えて下記の制約も満たす.

  • 答えは 10 以下である.

入出力例

入力例 1

5 3.000
1.000 0.000
0.000 0.000
-1.000 0.000
10.000 0.000
-10.000 0.000

出力例 1

3

家屋 1,2,3 と家屋 4 と家屋 5 で表札が異なる.全体で 3 つの表札が存在する.

入力例 2

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

出力例 2

7

入力例 3

5 99.999
0.000 0.000
49.999 0.001
0.000 0.000
-49.999 -0.001
0.000 0.000

出力例 3

1

Writer: 楠本充
Tester: 小浜翔太郎

Source: Kyoto University Programming Contest 2012 , Kyoto, Japan, 2012-07-01
http://www.kupc.jp/
http://kupc2012.contest.atcoder.jp/