AT_arc010_4 [ARC010D] 情報伝播

[problemUrl]: https://atcoder.jp/contests/arc010/tasks/arc010_4 $ AtCoder $ 国の秘密情報部に就職した青木くんは諜報活動に勤しむ青年です。 今回、青木くんに与えられたミッションは以下の様なものです。 - 青木くんは $ 2 $ 次元座標上に散らばる全ての仲間に $ AtCoder $ 国の機密情報を伝えなければならない。 - ただし、その $ 2 $ 次元座標上には仲間だけでなく、敵国のスパイが紛れ込んでいる。 - 青木くんが仲間に機密情報を伝えると、情報を受け取った仲間はスピーカーで情報を拡散する（機密情報だというのに！） - スピーカーで情報を拡散するとは、自分を中心とする同心円状内（スピーカーの音量は調節できるので、半径は任意である）にいる全ての「人間」に情報を伝えることである。 - 情報を受け取った仲間もスピーカーで情報を拡散し、連鎖的に情報を伝えていく。 - 当然のことながらスパイに機密情報が伝わってはいけない。 このミッションを達成するために、青木くんは全ての仲間の場所に赴いて 1. 機密情報を伝える 2. 持っているスピーカーを叩き潰す 3. 「機密情報を漏らすな」と念を押す この $ 3 $ つを行えば良いのですが、残念ながら全ての仲間の場所へ赴くような時間はありません。 そこで、青木くんは仲間がスピーカーで情報を拡散してしまう性質を利用して、効率良く機密情報を伝えてもらうことにしました。 スパイに機密情報が漏れることなく、全ての仲間に機密情報を伝えるとき、青木くんが機密情報を伝えなければならない仲間の最小の人数はいくらでしょうか。 入力は以下の形式で標準入力から与えられる。 > $ N $ $ f_{x1} $ $ f_{y1} $ $ f_{x2} $ $ f_{y2} $ $ : $ $ : $ $ f_{xN} $ $ f_{yN} $ $ M $ $ s_{x1} $ $ s_{y1} $ $ s_{x2} $ $ s_{y2} $ $ : $ $ : $ $ s_{xM} $ $ s_{yM} $ - $ 1 $ 行目には仲間の数を表す整数 $ N $ が与えられ、 $ 1≦N≦5,000 $ を満たす。 - $ 2 $ 行目から $ N+1 $ 行目までの $ N $ 行で仲間の位置情報が与えられる。 1. $ f_{xi} $ は $ i $ 番目に与えられる仲間の $ X $ 座標である。 2. $ f_{yi} $ は $ i $ 番目に与えられる仲間の $ Y $ 座標である。 3. $ i $ は $ 1≦i≦N $ を満たし、 $ f_{xi} $ と $ f_{yi} $ はそれぞれ $ -10^9≦f_{xi} $ $ , $ $ f_{yi}≦10^9 $ を満たす整数である。 12. $ N+2 $ 行目にはスパイの数を表す整数 $ M $ が与えられ、 $ 0≦M≦100,000 $ を満たす。 13. $ N+2 $ 行目から $ N+M+2 $ 行目までの $ M $ 行でスパイの位置情報が与えられる。 1. $ s_{xj} $ は $ j $ 番目に与えられるスパイの $ X $ 座標である。 2. $ s_{yj} $ は $ j $ 番目に与えられるスパイの $ Y $ 座標である。 3. $ j $ は $ 1≦j≦M $ を満たし、 $ s_{xj} $ と $ s_{yj} $ はそれぞれ $ -10^9≦s_{xj} $ $ , $ $ s_{yj}≦10^9 $ を満たす整数である。 15. 同じ座標に複数の人間が重なることはない。 16. $ M\ >\ 1,000 $ のとき、スパイはランダムに分布することが保証される。 - $ 0≦N≦10 $ を満たす入力にのみ正解した場合、部分点として $ 10 $ 点が与えられる。 - $ 0≦N≦30 $ を満たす入力にのみ正解した場合、部分点として $ 50 $ 点が与えられる。 情報を伝える必要がある最小の人数を出力せよ。 出力は標準出力におこない、末尾には改行をいれること。 ``` 3 1 1 1 2 2 1 0 ``` ``` 1 ``` - 座標 $ (1,\ 1) $ にいる仲間に伝えることができれば、 $ 3 $ 人の仲間全員に伝えることができます。 ``` 2 1 1 1 2 1 2 1 ``` ``` 1 ``` - 座標 $ (1,\ 2) $ にいる仲間に伝えることができれば、 $ 2 $ 人の仲間全員に伝えることができます。 - 座標 $ (1,\ 1) $ にいる仲間から 座標 $ (1,\ 2) $ にいる仲間に伝えようとすると、必ずスパイに見つかってしまいます。 ``` 5 1 1 1 2 2 3 3 3 5 3 2 2 1 4 4 ``` ``` 2 ``` - 座標 $ (2,\ 3) $ にいる仲間に伝えることができれば、座標 $ (1,\ 2) $ にいる仲間と、座標 $ (3,\ 3) $ にいる仲間へ情報を伝えることができます。 - その後、座標 $ (1,\ 2) $ にいる仲間から座標 $ (1,\ 1) $ にいる仲間へ情報が伝搬されます。 - 座標 $ (5,\ 3) $ にいる仲間へは、別途情報を伝える必要があります。 ``` 10 -10 5 2 9 -4 4 10 -9 8 3 5 6 4 -5 6 8 -8 10 -4 -2 10 -1 2 -2 -7 9 -3 -5 5 6 -10 -10 9 7 4 2 1 -10 1 -5 2 ``` ``` 8 ```

N/A

N/A