C - 白蛇のお守り Editorial

Time Limit: 2 sec / Memory Limit: 256 MB

問題

昔々あるところに白蛇のお守りをつけた巫女さんがおりました。 彼女の名前は現代に伝えられていないため、今ではMiss.Pythonと呼ばれています。 ある時、村に邪悪な霊の大軍勢が跳梁跋扈し、村々に大きな災いが降りかかりました。 そんな中、Miss.Pythonが、蛇のお守りを掲げると、突然輝きだして、一直線に光が走ったかと思うと、光は次々に邪霊を浄化し、終いには元締めを貫いて浄化してしまいました。 お守りの光は、元締めを貫いたところで消えてしまいました。 元締めが浄化されると、周辺の邪霊も消え、村々は災いから救われたそうな。

あなたは、夏休みの自由研究で、この昔話について調べています。 古文書には、おびただしい数の邪霊がどこに浮遊していたか、克明に記載されておりました!? その中には、Miss.Pythonが居たと思われる神社や邪霊の元締めの位置まで記されていました。

そこであなたは、お守りの光が浄化したという邪霊の数について興味を持ち、調べてみることにしました。

入力

入力は以下の形式で標準入力から与えられる。
入力制約について追記いたしました。

NN NXNX NYNY QXQX QYQY
WAX1WAX_1 WAY1WAY_1 WBX1WBX_1 WBY1WBY_1
:
WAXN1WAX_{N-1} WAYN1WAY_{N-1} WBXN1WBX_{N-1} WBYN1WBY_{N-1}
  1. 1行目には整数 N,NX,NY,QX,QYN, NX, NY, QX, QY が与えられます。
    • NN は邪霊の数を表します。
    • NXNX はMiss.Pythonの XX 座標を表します。
    • NYNY はMiss.Pythonの YY 座標を表します。
    • QXQX は邪霊の元締めの XX 座標を表します。
    • QYQY は邪霊の元締めの YY 座標を表します。
    • 1N10,0001 ≦ N ≦ 10,000 であることは保証されています。
    • 1,000NX,NY,QX,QY1,000-1,000 ≦ NX, NY, QX, QY ≦ 1,000 であることは保証されています。
    • Miss.Pythonと邪霊の元締めの位置は異なることが保証されています。
  2. 2行目から NN 行目までの N1N-1 行では、元締め以外の邪霊の両端の XX 座標および YY 座標がそれぞれ半角スペース区切りで与えられます。
    • 元締め以外の邪霊は雲のように漂っている感じなので線分で表します。
    • WAXiWAX_iii 番目の元締め以外の邪霊の両端 AAXX 座標を表します。
    • WAYiWAY_iii 番目の元締め以外の邪霊の両端 AAYY 座標を表します。
    • WBXiWBX_iii 番目の元締め以外の邪霊の両端 BBXX 座標を表します。
    • WBYiWBY_iii 番目の元締め以外の邪霊の両端 BBYY 座標を表します。
    • 1,000WAXi,WAYi,WBXi,WBYi1,000-1,000 ≦ WAX_i, WAY_i, WBX_i, WBY_i ≦ 1,000 であることは保証されています。
    • WAXiWBXiWAX_i \neq WBX_i または WAYiWBYiWAY_i \neq WBY_i であることは保証されています。
    • どの元締め以外の邪霊もMiss.Pythonと重ならないことは保証されています。
    • どの元締め以外の邪霊も邪霊の元締めと重ならないことは保証されています。
    • 元締め以外の邪霊の両端の XX 座標および YY 座標は整数で与えられます。

出力

お守りの光が貫いた邪霊の数を1行に出力すること。
なお、お守りの光や邪霊の大きさは考えないものとし、お守りの光と邪霊が接する場合は貫いたものとみなす。

入力例

4 1 1 4 4
1 2 2 1
2 3 3 2
3 4 4 3

出力例

4

Source Name

Maximum-Cup 2013


2025-04-04 (Fri)
23:49:26 +00:00