← 返回题目列表

AtCoder · joisc2017_l

L. 龙2

中文机器翻译题面 查看原题

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

ドラゴン 2 (Dragon 2) - 原题 PDF 第 1 页
原题PDF第11页
ドラゴン 2 (Dragon 2) - 原题 PDF 第 2 页
原题PDF第12页
ドラゴン 2 (Dragon 2) - 原题 PDF 第 3 页
原题PDF第13页
ドラゴン 2 (Dragon 2) - 原题 PDF 第 4 页
原题PDF第14页
可复制的 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