No.2353 Guardian Dogs in Spring

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

No.2353 Guardian Dogs in Spring

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題（複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 143
作問者 : 👑

AngrySadEight / テスター :

kumakuma

Shirotsume 👑

seekworser

13 ProblemId : 9391 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2023-05-12 09:54:42

問題文

$N$ 体の狛犬が， $xy$ 座標上にいます． $i(1 \leq i \leq N)$ 体目の狛犬は座標 $(x_i, y_i)$ におり，はじめ全ての狛犬は $x$ 軸の正の向きを向いています．

2 体の狛犬は，次の条件を満たしているときに，向かい合っている狛犬の組となります．

2 体の狛犬は，互いに一方がもう一方の狛犬の方向を向いている．
2 体の狛犬の間を線分で結んだとき，その線分上にほかの狛犬はいない．

あなたは，全ての狛犬に対し，向きを自由に変えることができます．向かい合っている狛犬の組の数を最大化してください．

制約

入力はすべて整数である．
$2 \leq N \leq 8000$
$0 \leq x_i, y_i \leq 8000$
$(x_i, y_i) \neq (x_j, y_j)(i \neq j)$

入力

入力は以下の形式で標準入力から与えられる．

 $N$ 
 $x_1$   $y_1$ 
 $x_2$   $y_2$ 
 $\cdots$ 
 $x_N$   $y_N$

出力

向かい合っている狛犬の組の数を $K$ とし，以下の形式で $K+1$ 行出力せよ．すなわち，

$1$ 行目には，向かい合っている狛犬の組の数を出力せよ．
$2$ 行目から $K+1$ 行目には，向かい合っている狛犬の番号の組 $(z_1, w_1), (z_2, w_2), \dots, (z_K, w_K)$ を，各行に一組ずつ出力せよ．

 $K$ 
 $z_1$   $w_1$ 
 $z_2$   $w_2$ 
 $\cdots$ 
 $z_K$   $w_K$

サンプル

サンプル1

入力

出力

1
1 2

以下では， $i$ 体目の狛犬を以下では「狛犬 $i$ 」と呼びます．

狛犬の配置と，向かせる向きは下の図のようになります．

狛犬 $1$ と狛犬 $2$ を向かい合わせるように配置すると，向かい合っている狛犬の組は $1$ 組でき，これが最大となります．

残った狛犬 $3$ を狛犬 $2$ の方向に向かせることもできますが，狛犬 $2$ が狛犬 $3$ の方向を向いていないため，これは向かい合っている狛犬の組とはならないことに注意してください．

サンプル2

入力

出力

2
1 4
2 3

狛犬の配置と，向かせる向きは下の図のようになります．

狛犬 $1$ と狛犬 $4$ ，狛犬 $2$ と狛犬 $3$ を向かい合わせるように配置すると，向かい合っている狛犬の組は $2$ 組でき，これが最大となります．

一方，以下のような出力は不正解となります．

2
1 3
2 4

この場合，狛犬 $1$ と狛犬 $3$ を結ぶ線分上に狛犬 $2$ がいるため，条件を満たさなくなってしまいます．

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

yukicoder

No.2353 Guardian Dogs in Spring

問題文

制約

入力

出力

サンプル

サンプル1

入力

出力

サンプル2

入力

出力