問題一覧 > 通常問題

No.202 Throwing 1-Yen Coins

レベル : / AI推定難易度 : 900 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 159
作問者 : 👑 tails
お気に入りにしたユーザー ProblemId : 476 / 自分の提出
問題文最終更新日: 2020-08-27 16:06:41
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 102 (順位表) の他の問題:

Problem Statement

Yuki is playing by throwing the large number of 1-yen coins she has onto the floor of her room, one at a time.

When a thrown coin comes to rest on the floor, if it has stopped overlapping, even slightly, with a coin
already thrown and on the floor, that thrown coin is removed
before the next coin is thrown.
Otherwise, that is, if the thrown coin has stopped without overlapping any coin on the floor at all,
the thrown coin is left on the floor as it is.
(In this case, the thrown coin is assumed never to move afterward.)

Yuki has already finished throwing coins $N$ times. Now, how many
1-yen coins are on the floor?

Note the following.
A thrown coin always comes to rest lying flat on the floor (or on top of a coin on the floor).

A 1-yen coin is a circle of radius $10$. Its thickness is ignored.
When the circles of two coins are exactly externally tangent to each other, those two coins
are considered not to overlap.
For each of the $N$ throws, the center of the coin's circle at the moment it came to rest
is recorded as coordinates on the floor.

Input

$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$ are all integers.

$N$ is the number of times a 1-yen coin was thrown.
The center of the circle of the coin thrown $i$-th, when it came to rest, is at $(X_i, Y_i)$.

Output

Output the number of 1-yen coins on the floor after the $N$ throws are finished.

Sample

Sample 1
Input
3
0 0
15 0
30 0
Output
2

The 1st throw cannot overlap any other coin, so it always remains.
The 2nd throw overlaps the coin from the 1st throw, so it is removed.
The 3rd throw does not overlap any other coin, so it remains (the 2nd throw, already removed, does not matter).
In the end, the 2 coins from the 1st and 3rd throws remain, so the answer is 2.

Sample 2
Input
3
15 0
0 0
30 0
Output
1

The number of throws and the coin positions are the same as in Sample 1, but the order is different.
In this case, only 1 coin remains.

Sample 3
Input
2
100 100
112 116
Output
2

The two coins are exactly touching, but they do not overlap, so both remain.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。