問題一覧 > 通常問題

No.1265 Balloon Survival

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 209
作問者 : stoq / テスター : nok0
お気に入りにしたユーザー ProblemId : 5097 / 自分の提出
問題文最終更新日: 2021-03-31 09:53:05
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 271 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。