No.2353 Guardian Dogs in Spring
タグ : / 解いたユーザー数 143
作問者 : 👑
AngrySadEight
/ テスター :
kumakuma
Shirotsume
👑 
seekworser
問題文
$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
入力
3 1 1 2 1 3 2
出力
1 1 2
以下では，$i$ 体目の狛犬を以下では「狛犬 $i$ 」と呼びます．
狛犬の配置と，向かせる向きは下の図のようになります．
狛犬 $1$ と狛犬 $2$ を向かい合わせるように配置すると，向かい合っている狛犬の組は $1$ 組でき，これが最大となります．
残った狛犬 $3$ を狛犬 $2$ の方向に向かせることもできますが，狛犬 $2$ が狛犬 $3$ の方向を向いていないため，これは向かい合っている狛犬の組とはならないことに注意してください．
サンプル2
入力
4 1 1 2 2 3 3 4 2
出力
2 1 4 2 3
狛犬の配置と，向かせる向きは下の図のようになります．
狛犬 $1$ と狛犬 $4$，狛犬 $2$ と狛犬 $3$ を向かい合わせるように配置すると，向かい合っている狛犬の組は $2$ 組でき，これが最大となります．
一方，以下のような出力は不正解となります．
2 1 3 2 4
この場合，狛犬 $1$ と狛犬 $3$ を結ぶ線分上に狛犬 $2$ がいるため，条件を満たさなくなってしまいます．
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。