No.202 Throwing 1-Yen Coins
タグ : / 解いたユーザー数 159
作問者 : 👑
tails
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もしくは右上の雲マークをクリックしてアカウントを作成してください。