No.1121 Social Distancing in Cinema
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 43
作問者 :
e869120
/ テスター :
Thistle
タグ : / 解いたユーザー数 43
作問者 :
e869120
/ テスター :
Thistle
問題文最終更新日: 2020-07-22 21:35:14
問題文
Yuki 映画館には $1, 2, 3, ..., N$ と番号付けられた $N$ 個の座席が設置されており、番号 $i$ の座席は座標 $(x_i, y_i)$ にある。
今、新型のウイルスの影響で、映画館が閉鎖されている。再びオープンするためには、社会的距離を保ちながら運用する手段を考えなければならない。具体的には以下の通りである。
- $N$ 個の座席の中から $K$ 個の座席を選び、それらの座席のみに座らせる。
- $K$ 席すべてに人が座っている場合でも、どの人とどの人の間の距離も $10$ 以上でなければならない。（距離 $10$ 丁度でも問題ない。）
ただし、ここでの「距離」はユークリッド距離とする。つまり、座標 $(a, b)$ から座標 $(c, d)$ までの距離 $D$ は以下の通りである。 $$D = \sqrt{(a-c)^{2} + (b-d)^{2}}$$ そこで、$\frac{N}{90} \leq K$ となるような座席の選び方を $1$ つ出力しなさい。 ただし、与えられる制約の下では条件を満たす座席の選び方は必ず存在することが証明できます（21:32 追記）
入力
$N$ $X_1$ $Y_1$ $X_2$ $Y_2$ $X_3$ $Y_3$ ... $X_N$ $Y_N$
$N+1$ 行に渡って入力が与えられる。
$1$ 行目に、整数 $N$ が与えられる。
$1+i$ $(1 \leq i \leq N)$ 行目に、整数 $X_i, Y_i$ が空白区切りで与えられる。
出力
以下の形式で出力しなさい。ただし、この出力形式は、番号 $B_1, B_2, ..., B_K$ の席を選んで、その席のみに座らせることを意味する。
$K$ $B_1$ $B_2$ $B_3$ ... $B_K$
ここで、出力は以下の条件を満たす必要がある。
- 出力する値は全て整数
- $\frac{N}{90} \leq K$
- $1 \leq B_i \leq N$
- $B_i$ は全て異なる。つまり、$B_i \neq B_j$ $(i \neq j)$
- どの選んだ座席と選んだ座席の間の距離も、$10$ 以上である。
制約
- $1 \leq N \leq 250 \ 000$
- $1 \leq X_i, Y_i \leq 500$
- $(X_i, Y_i) \neq (X_j, Y_j)$ $(i \neq j)$
- 入力はすべて整数
サンプル
サンプル1
入力
4 1 1 1 9 9 1 9 9
出力
2 1 4
$\frac{N}{90} = 0.044444...$ 席以上を選んでいるため、正解となる。
なお、座席 $1$ と $4$ の距離は $\sqrt{(1-9)^2+(1-9)^2} = 11.3137... \geq 10$ となり、条件を満たす。
サンプル2
入力
9 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3
出力
1 5
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。