No.202 1円玉投げ

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 96
作問者 : tailstails

4 ProblemId : 476 / 出題時の順位表

問題文

ユキさんは、手元にある大量の1円玉を1枚ずつ部屋の床に投げて遊んでいます。

投げた1円玉が床の上で止まったとき、それが既に投げられた床の上の1円玉と
少しでも重なって止まった場合には、次の1円玉を投げる前に、その投げた1円玉を
取り除きます。
そうではない場合、すなわち、投げた1円玉が床の上の1円玉と全く重ならずに
止まった場合には、その投げた1円玉をそのまま床の上に残します。
(この場合、その投げた1円玉はそれ以降ずっと移動しないものとします)。

ユキさんは、すでに1円玉を$N$回投げ終えました。さて、床の上には何枚の
1円玉があるでしょうか?

なお、
投げた1円玉は、床の上(または床の上の1円玉の上)に、必ず倒れた状態で
止まるものとします。
1円玉は円形とし、半径は$10$とします。厚みは無視します。
2つの1円玉の円がちょうど互いに外接する状態では、それら2つの1円玉は
重なっていないものとします。
$N$回投げたそれぞれの1円玉が止まった時の円の中心位置が、
床面上の座標として記録されています。

入力

$N$
$X_1$ $Y_1$
$X_2$ $Y_2$
⋮
$X_N$ $Y_N$

$1 \le N \le 100000 = 10^5$
$0 \le X_i, Y_i \le 20000$
$N$, $X_i$, $Y_i$ はいずれも整数です。

$N$ は、1円玉を投げた回数です。
$i$ 回目に投げた1円玉が止まったときの円の中心座標は $(X_i, Y_i)$ です。

出力

1円玉を$N$回投げ終えた後に床の上にある1円玉の数を出力してください。

サンプル

サンプル1
入力
3
0 0
15 0
30 0
出力
2

1投目は、他の1円玉に重なることはありませんので、必ず残ります。
2投目は、1投目の1円玉に重なったので、取り除かれます。
3投目は、他の1円玉に重なっていないので残ります(既に取り除かれている2投目は関係ありません)。
結局、1投目と3投目の2枚が残るので、答えは2になります。

サンプル2
入力
3
15 0
0 0
30 0
出力
1

投げた回数と1円玉の位置はサンプル1と同じですが、順序が異なります。
この場合は1枚しか残りません。

サンプル3
入力
2
100 100
112 116
出力
2

2枚の1円玉はちょうど接していますが、重なっていないので、両方とも残ります。

提出ページヘ