Problem D
地下鉄計画
Languages
en
ja
ある国の政府が、首都に地下鉄システムを設置する可能性を検討しています。現実的な理由から、各地下鉄路線は中央駅を起点にして、任意の角度に直線的に進むようにしたいと考えているようです。あなたはそのような方法が可能かどうかを調査するために雇われました。市内の重要な場所の座標と、これらの場所と地下鉄駅(おそらくすでに建設されている中央駅)との距離が遠いことから、あなたの仕事は、必要とされる最小の路線数を計算することです。なお、駅は路線に沿っていくつでも建設できます。
入力
入力ファイルの最初の行には、データセットの数を表す整数 $N$ が含まれています。それぞれのデータセットは、$n$と$d$の2つの整数 ($1 \le n \le 500$, $0 \le d < 150$) で始まります。$n$は、地下鉄の駅が近くになければならない重要な場所の数、$d$は、重要な場所と地下鉄の駅との間の最大距離です。 次の$n$行は、重要な場所の座標を表す$x$と$y$の2つの整数($-100 \le x, y \le 100$)が含まれています。中央駅の座標は $0,0$ です。データセットの中の座標のすべてのペアは異なる値です(そして、どれも$0,0$にはなりません)。
出力
各データセットについて、1行に1つの整数を出力します。すべての重要な場所が地下鉄駅から最大$d$の距離にあるために必要な地下鉄の最低本数です。
サンプル入力 1 | サンプル出力 1 |
---|---|
2 7 1 -1 -4 -3 1 -3 -1 2 3 2 4 2 -2 6 -2 4 0 0 4 -12 18 0 27 -34 51 |
4 2 |