No.2652 [Cherry 6th Tune N] Δρονε χιρχλινγ
タグ : / 解いたユーザー数 60
作問者 : 👑 Kazun / テスター : 👑 AngrySadEight
ストーリー
マンハッタンに住んでいるオスバチ忍者のチェリーくんはドローンを飛ばすことを趣味にしています. 今日もチェリーくんはいろんな所へ向かってドローンを飛ばしてます.
充電が切れないようにするためにも, 空よりも高いところにいるチェリーくんにアドバイスしてあげましょう.
問題文
$xy$ 上の正方形領域 $R$ を $R:=\{(x,y) \mid 0 \leq x \leq L, 0 \leq y \leq L\}$ で定める. この $R$ 内をドローンが飛行する.
$R$ 内には $N$ 個のチェックポイントがあり, $i~(1 \leq i \leq N)$ 番目のチェックポイント $P_i$ は座標 $(X_i, Y_i)$ にある.
ここで, $xy$ 平面上の $2$ つの点 $S=(x,y), S'=(x', y')$ において, $S$ から $S'$ へドローンが移動するために必要なコスト $\operatorname{cost}(S,S')$ は $$\operatorname{cost}(S,S')=\lvert x-x' \rvert+\lvert y-y' \rvert $$ である.
以下を満たすような $R$ 内の点の列 $A=(A_1, A_2, \dots, A_M)$ の一例を挙げよ.
- $1 \leq M \leq 2N$.
- $A_j$ の $x$ 座標, $y$ 座標は共に整数である $\quad (1 \leq j \leq M)$.
- $A_j \in R \quad (j=1,2, \dots, M)$.
- $A_1, A_2, \dots, A_M$ の中に, $P_i$ が $1$ 回以上現れる $\quad (1 \leq i \leq N)$.
- $A_1 \to A_2 \to \dots \to A_{M-1} \to A_M \to A_1$ の順にドローンが移動するとき, コストの総和は $1000 L$ 以下である.つまり, $$\sum_{j=1}^{M-1} \operatorname{cost} (A_j, A_{j+1})+\operatorname{cost}(A_M, A_1) \leq 1000L$$ である.
なお, この問題の制約下では, 正解となるような $A$ が存在することが証明できる.
$T$ 個のテストケースについて答えよ.
制約
- $1 \leq T \leq 10^5$.
- 各テストケースに関する制約.
- $2 \leq N \leq 2 \times 10^5$.
- $1 \leq L \leq 10^9$
- $0 \leq X_i \leq L, 0 \leq Y_i \leq L \quad (1 \leq i \leq N)$.
- $i \neq j \Rightarrow (X_i, Y_i) \neq (X_j, Y_j) \quad (1 \leq i \leq N, 1 \leq j \leq N)$.
- テストファイルに関する制約.
- $T$ 個のテストケースにおける $N$ の総和は $2 \times 10^5$ 以下である.
- 入力は全て整数である.
入力
$T$ ${\rm Testcase}_1$ ${\rm Testcase}_2$ $\vdots$ ${\rm Testcase}_T$
$N$ $L$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_N$ $Y_N$
出力
各テストケースについて, 解答する $A=(A_1,A_2, \dots, A_M)$ において, $A_j$ の座標を $(x_j, y_j)$ とするとき, 以下の形式で出力せよ.
$M$ $x_1$ $y_1$ $x_2$ $y_2$ $\vdots$ $x_M$ $y_M$
サンプル
サンプル1
入力
2 4 6 0 1 4 2 5 3 3 1 3 1000000000 0 0 1000000000 0 1000000000 1000000000
出力
7 3 5 0 1 2 6 5 3 3 1 4 2 1 4 5 0 0 0 1000000000 1000000000 1000000000 1000000000 0 1000000000 1000000000
- [第 $1$ テストケース] $A_1, A_2, \dots, A_7$ の中に $P_1, P_2, P_3, P_4$ がそれぞれ $1$ 回以上現れる.
例えば, $A_1=(3,5)$ から $A_2=(0,1)$ へドローンが移動するコストは $\operatorname{cost}(A_1, A_2)=\lvert 3-0 \rvert+\lvert 5-1 \rvert =7$ である.
ドローンが $A_1 \to A_2 \to \dots \to A_6 \to A_7 \to A_1$ の順に通るとき, そのコストの総和は $34$ であり, $1000L=6000$ 以下である. - [第 $2$ テストケース] $A_1, A_2, \dots, A_M$ の中に同じ地点があっても構わない.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。