問題一覧 > 通常問題

No.1265 Balloon Survival

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 162
作問者 : 👑 stoqstoq / テスター : nok0nok0
15 ProblemId : 5097 / 出題時の順位表
問題文最終更新日: 2020-10-22 18:57:56

問題文

$N$ 個の風船が座標平面上に設置されています。 風船は円とみなせ、 $i$ 番目の風船の中心座標は $(x_i,\ y_i)$ 、半径は0です。

合図を送ると風船に空気が送られ、すべての風船が一斉に毎秒1の速さで半径を拡大させます。このとき中心座標は変化しません。

風船はとても繊細なため、2つの風船が接触するとどちらも破裂し消滅します。3つ以上の風船が同時に接触し合うことはありません (同時刻に2回以上の接触が起こることはあります)。 風船の膨張は風船が1個以下になるまで続きます。

あなたは合図を送る前に、いくつかの風船を取り除くことが出来ます。 合図を送った後1番目の風船だけを残すために、取り除く必要のある風船の最小個数を求めてください。

入力

$N$
$x_1\ y_1$
$\vdots$
$x_N\ y_N$

  • 入力は全て整数
  • $1 \leq N \leq 1000$
  • $|x_i|,|y_i| \leq 10^8$
  • $i \neq j$ ならば $(x_i,\ y_i) \neq (x_j,\ y_j)$
  • 最初の取り除き方によらず、3つ以上の風船が同時に接触し合うことはない

出力

1番目の風船のみを残すために取り除く必要のある風船の最小個数を出力してください。

サンプル

サンプル1
入力
3
0 0
5 1
5 -1
出力
0

最初に風船を取り除かずとも、合図を送ってから1秒後に風船2と風船3が接触し破裂するため、これが最適です。

サンプル2
入力
2
1 1
2 2
出力
1

2番目の風船を取り除くほかありません。

サンプル3
入力
1
0 0
出力
0

サンプル4
入力
10
0 -6
11 15
-12 -3
-6 9
5 8
1 -11
2 13
3 8
-4 7
15 -7
出力
3

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