以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。




可复制的 PDF 提取文本
The 16th Japanese Olympiad in Informatics (JOI 2016/2017)
Spring Training Camp/Qualifying Trial
March 19–25, 2017 (Komaba/Yoyogi, Tokyo)
Contest Day 4 – Dragon 2
ドラゴン2 (Dragon 2)
JOI 平原では,人々はドラゴンたちと共に生きている.
JOI 平原は広大な座標平面であり,直交するX 軸とY 軸が設定されている.X 座標がx, Y 座標がy の
点を(x, y) で表す.
JOI 平原にはN 匹のドラゴンが生息しており,1 からN の番号が付けられている.また,ドラゴンには
M 種の種族があり,1 からM の番号が付けられている.ドラゴンi (1 ≦i ≦N) は常にJOI 平原の点(Ai, Bi)
におり,その種族はCi である.JOI 平原には,すべての種族のドラゴンが生息しているとは限らない.
JOI 平原には人間の住む村が2 つあり,それぞれJOI 平原の点(D1, E1) および点(D2, E2) に位置する.2
つの村は道で結ばれており,その道は村が存在する2 点を結ぶ線分である.
点(A1, B1), . . . , (AN, BN) および点(D1, E1), (D2, E2) は,互いに異なり,これらの内のどの3 点も同一直線
上にない.
ドラゴンたちはしばしば種族間で対立する.種族a (1 ≦a ≦M) が種族b (1 ≦b ≦M, a , b) に対して敵
意を抱くと,種族a に属するそれぞれのドラゴンが,種族b に属するすべてのドラゴンに向けて火の玉を
吐く.火の玉は標的のドラゴンに向かって直進し,標的に到達したあとも同じ方向に飛び去っていく.す
なわち,火の玉の辿る経路は半直線である.
種族間対立の際に,ドラゴンの吐いた火の玉が道を横切れば,道はダメージを受けるだろう.あなたは
近い将来に起こりうるドラゴンたちの種族間対立として,考えられるQ 個の可能性をリストアップした.
想定される種族間対立のそれぞれについて,道を横切る火の玉の個数を求めたい.
課題
ドラゴンたちおよび人間の村の情報と,ドラゴンたちの種族間対立の可能性のリストが与えられるとき,
それぞれの種族間対立について,道を横切る火の玉の個数を求めるプログラムを作成せよ.
入力
標準入力から以下のデータを読み込め.
• 1 行目には,2 個の整数N, M が空白を区切りとして書かれている.これは,JOI 平原にはドラゴンが
N 匹おり,M 種の種族に分かれていることを表す.
• 続くN 行のうちのi 行目(1 ≦i ≦N) には,3 個の整数Ai, Bi,Ci が空白を区切りとして書かれている.
これは,ドラゴンi がJOI 平原の点(Ai, Bi) におり,種族がCi であることを表す.
• 次の行には,4 個の整数D1, E1, D2, E2 が空白を区切りとして書かれている.これは,人間の住む村
がJOI 平原の点(D1, E1) および点(D2, E2) に位置していることを表す.
• 次の行には,整数Q が書かれている.これは,想定される種族間対立がQ 個あることを表す.
ドラゴン2– 1 / 4
The 16th Japanese Olympiad in Informatics (JOI 2016/2017)
Spring Training Camp/Qualifying Trial
March 19–25, 2017 (Komaba/Yoyogi, Tokyo)
Contest Day 4 – Dragon 2
• 続くQ 行のうちのj 行目(1 ≦j ≦Q) には,2 個の整数F j,G j が空白を区切りとして書かれている.
これは,想定される種族間対立のj 個目において,種族F j が種族G j に対して敵意を抱くことを表す.
出力
出力はQ 行からなる.標準出力のj 行目(1 ≦j ≦Q) には,j 個目の種族間対立において道を横切る火の
玉の個数を出力せよ.
制限
すべての入力データは以下の条件を満たす.
• 2 ≦N ≦30 000.
• 2 ≦M ≦N.
• −1 000 000 000 ≦Ai ≦1 000 000 000 (1 ≦i ≦N).
• −1 000 000 000 ≦Bi ≦1 000 000 000 (1 ≦i ≦N).
• 1 ≦Ci ≦M (1 ≦i ≦N).
• −1 000 000 000 ≦D1 ≦1 000 000 000.
• −1 000 000 000 ≦E1 ≦1 000 000 000.
• −1 000 000 000 ≦D2 ≦1 000 000 000.
• −1 000 000 000 ≦E2 ≦1 000 000 000.
• N + 2 個の点(A1, B1), . . . , (AN, BN), (D1, E1), (D2, E2) は互いに異なり,どの3 点も同一直線上にない.
• 1 ≦Q ≦100 000.
• 1 ≦F j ≦M (1 ≦j ≦Q).
• 1 ≦G j ≦M (1 ≦j ≦Q).
• F j , G j (1 ≦j ≦Q).
• (F j,G j) , (Fk,Gk) (1 ≦j < k ≦Q).
ドラゴン2– 2 / 4
The 16th Japanese Olympiad in Informatics (JOI 2016/2017)
Spring Training Camp/Qualifying Trial
March 19–25, 2017 (Komaba/Yoyogi, Tokyo)
Contest Day 4 – Dragon 2
小課題
この課題では小課題は全部で3 個ある.各小課題の配点および追加の制限は以下の通りである.
小課題1 [15 点]
• N ≦3 000.
小課題2 [45 点]
• Q ≦100.
小課題3 [40 点]
追加の制限はない.
入出力例
入力例1 出力例1
4 2 1
0 1 1 2
0 -1 1
1 2 2
-6 1 2
-2 0 2 0
2
1 2
2 1
1 個目の種族間対立では,
• ドラゴン1 がドラゴン3 に向けて吐いた火の玉は道を横切らない.
• ドラゴン1 がドラゴン4 に向けて吐いた火の玉は道を横切らない.
• ドラゴン2 がドラゴン3 に向けて吐いた火の玉は道を横切る.
• ドラゴン2 がドラゴン4 に向けて吐いた火の玉は道を横切らない.
よって道を横切る火の玉は1 個である.
2 個目の種族間対立では,
• ドラゴン3 がドラゴン1 に向けて吐いた火の玉は道を横切る.
ドラゴン2– 3 / 4
The 16th Japanese Olympiad in Informatics (JOI 2016/2017)
Spring Training Camp/Qualifying Trial
March 19–25, 2017 (Komaba/Yoyogi, Tokyo)
Contest Day 4 – Dragon 2
• ドラゴン3 がドラゴン2 に向けて吐いた火の玉は道を横切る.
• ドラゴン4 がドラゴン1 に向けて吐いた火の玉は道を横切らない.
• ドラゴン4 がドラゴン2 に向けて吐いた火の玉は道を横切らない.
よって道を横切る火の玉は2 個である.
入力例2 出力例2
3 2 1
-1000000000 -1 1
-999999998 -1 1
0 0 2
999999997 1 999999999 1
1
1 2
入力例3 出力例3
6 3 4
2 -1 1 2
1 0 1 4
0 3 2 0
2 4 2 2
5 4 3 1
3 9 3
0 0 3 3
6
1 2
1 3
2 1
2 3
3 1
3 2
ドラゴン2– 4 / 4