No.1265 Balloon Survival
Problem Statement
$N$ balloons are placed on the coordinate plane. Each balloon can be regarded as a circle; the center of the $i$-th balloon is at $(x_i,\ y_i)$ and its radius is 0.
When a signal is sent, air is pumped into the balloons, and all balloons simultaneously expand their radii at a speed of 1.0 per second. The center coordinates do not change during this process.
The balloons are very delicate, so when two balloons touch, both of them burst and disappear. Three or more balloons never touch one another at the same time (two or more separate contacts may occur at the same time). The balloons keep expanding until at most 1 balloon remains.
Before sending the signal, you may remove some of the balloons. Find the minimum number of balloons that must be removed so that only the 1st balloon remains after the signal is sent.
Input
$N$ $x_1\ y_1$ $\vdots$ $x_N\ y_N$
- All input values are integers.
- $1 \leq N \leq 1000$
- $|x_i|,|y_i| \leq 10^8$
- If $i \neq j$, then $(x_i,\ y_i) \neq (x_j,\ y_j)$
- Regardless of how the balloons are initially removed, three or more balloons never touch one another at the same time.
Output
Output the minimum number of balloons that must be removed so that only the 1st balloon remains.
Sample
Sample 1
Input
3 0 0 5 1 5 -1
Output
0
Even without removing any balloons initially, balloon 2 and balloon 3 touch and burst 1 second after the signal is sent, so this is optimal.
Sample 2
Input
2 1 1 2 2
Output
1
There is no choice but to remove the 2nd balloon.
Sample 3
Input
1 0 0
Output
0
Sample 4
Input
10 0 -6 11 15 -12 -3 -6 9 5 8 1 -11 2 13 3 8 -4 7 15 -7
Output
3
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
stoq
nok0