AT_maximum_2013_c 白蛇のお守り

[problemUrl]: https://atcoder.jp/contests/maximum-cup-2013/tasks/maximum_2013_c 昔々あるところに白蛇のお守りをつけた巫女さんがおりました。 彼女の名前は現代に伝えられていないため、今ではMiss.Pythonと呼ばれています。 ある時、村に邪悪な霊の大軍勢が跳梁跋扈し、村々に大きな災いが降りかかりました。 そんな中、Miss.Pythonが、蛇のお守りを掲げると、突然輝きだして、一直線に光が走ったかと思うと、光は次々に邪霊を浄化し、終いには元締めを貫いて浄化してしまいました。 お守りの光は、元締めを貫いたところで消えてしまいました。 元締めが浄化されると、周辺の邪霊も消え、村々は災いから救われたそうな。 あなたは、夏休みの自由研究で、この昔話について調べています。 古文書には、おびただしい数の邪霊がどこに浮遊していたか、克明に記載されておりました！？ その中には、Miss.Pythonが居たと思われる神社や邪霊の元締めの位置まで記されていました。 そこであなたは、お守りの光が浄化したという邪霊の数について興味を持ち、調べてみることにしました。 入力は以下の形式で標準入力から与えられる。 入力制約について追記いたしました。 > $ N $ $ NX $ $ NY $ $ QX $ $ QY $ $ WAX_1 $ $ WAY_1 $ $ WBX_1 $ $ WBY_1 $ : $ WAX_{N-1} $ $ WAY_{N-1} $ $ WBX_{N-1} $ $ WBY_{N-1} $ 1. 1行目には整数 $ N,\ NX,\ NY,\ QX,\ QY $ が与えられます。 - $ N $ は邪霊の数を表します。 - $ NX $ はMiss.Pythonの $ X $ 座標を表します。 - $ NY $ はMiss.Pythonの $ Y $ 座標を表します。 - $ QX $ は邪霊の元締めの $ X $ 座標を表します。 - $ QY $ は邪霊の元締めの $ Y $ 座標を表します。 - $ 1\ ≦\ N\ ≦\ 10,000 $ であることは保証されています。 - $ -1,000\ ≦\ NX,\ NY,\ QX,\ QY\ ≦\ 1,000 $ であることは保証されています。 - Miss.Pythonと邪霊の元締めの位置は異なることが保証されています。 2. 2行目から $ N $ 行目までの $ N-1 $ 行では、元締め以外の邪霊の両端の $ X $ 座標および $ Y $ 座標がそれぞれ半角スペース区切りで与えられます。 - 元締め以外の邪霊は雲のように漂っている感じなので線分で表します。 - $ WAX_i $ は $ i $ 番目の元締め以外の邪霊の両端 $ A $ の $ X $ 座標を表します。 - $ WAY_i $ は $ i $ 番目の元締め以外の邪霊の両端 $ A $ の $ Y $ 座標を表します。 - $ WBX_i $ は $ i $ 番目の元締め以外の邪霊の両端 $ B $ の $ X $ 座標を表します。 - $ WBY_i $ は $ i $ 番目の元締め以外の邪霊の両端 $ B $ の $ Y $ 座標を表します。 - $ -1,000\ ≦\ WAX_i,\ WAY_i,\ WBX_i,\ WBY_i\ ≦\ 1,000 $ であることは保証されています。 - $ WAX_i\ \neq\ WBX_i $ または $ WAY_i\ \neq\ WBY_i $ であることは保証されています。 - どの元締め以外の邪霊もMiss.Pythonと重ならないことは保証されています。 - どの元締め以外の邪霊も邪霊の元締めと重ならないことは保証されています。 - 元締め以外の邪霊の両端の $ X $ 座標および $ Y $ 座標は整数で与えられます。 お守りの光が貫いた邪霊の数を1行に出力すること。 なお、お守りの光や邪霊の大きさは考えないものとし、お守りの光と邪霊が接する場合は貫いたものとみなす。 ``` 4 1 1 4 4 1 2 2 1 2 3 3 2 3 4 4 3 ``` ``` 4 ```

N/A

N/A