問題一覧 > 通常問題

No.2652 [Cherry 6th Tune N] Δρονε χιρχλινγ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 60
作問者 : 👑 KazunKazun / テスター : 👑 AngrySadEightAngrySadEight
0 ProblemId : 6009 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-02-23 21:36:56

ストーリー

マンハッタンに住んでいるオスバチ忍者のチェリーくんはドローンを飛ばすことを趣味にしています. 今日もチェリーくんはいろんな所へ向かってドローンを飛ばしてます.

充電が切れないようにするためにも, 空よりも高いところにいるチェリーくんにアドバイスしてあげましょう.

問題文

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