← 返回题目列表

AtCoder · joisc2008_flu

flu. 流感(流感)

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

以下是来自日本的官方新闻原版PDF,已经完整保存和染色。

インフルエンザ (Flu) - 原题 PDF 第 1 页
原始 PDF 第 4 部分
インフルエンザ (Flu) - 原题 PDF 第 2 页
原题PDF第5页
インフルエンザ (Flu) - 原题 PDF 第 3 页
原题PDF第6页
可复制的 PDF 提取文本
Flu: インフルエンザ


input ファイル“flu.in”
output 標準出力
ソースファイルflu.c/flu.cpp
時間制限1 秒/ データ


 今年はJOI 国でインフルエンザの大流行の兆しがある.JOI 国にはn 個の都市P1, . . . , Pn が

あり,都市Pi の場所は座標を用いてPi(xi, yi) と表される.異なる都市が同じ座標を持つことは

ない.すなわち,i ̸= j であれば,(xi, yi) ̸= (xj, yj) である.また,都市P1 は首都のJOI 市で

ある.

 今年のインフルエンザは特別な型であり,次のような特徴がある.

   1. 各都市において,インフルエンザの流行はちょうどm 日間続く.すなわち,もし都市Pi

   でインフルエンザの流行が始まったとすると,Pi におけるインフルエンザの流行はちょう

  どm 日間続き,m 日後にはインフルエンザの流行は収まる.

   2. ある都市で一度インフルエンザが流行すると,その都市の市民の体内に抗体ができる.そ

   のため,インフルエンザが1 つの都市で2 回以上流行することはない.

   3. インフルエンザは日を追うごとに都市から都市へと流行を拡大する.その感染可能距離

   はd である.もし,都市Pi でインフルエンザの流行が始まったとする.都市Pj とPi の

   距離がd 以下であり,まだPj ではインフルエンザは流行していない場合,その翌日に

   は,都市Pj でインフルエンザの流行が始まる.(都市Pi(xi, yi) とPj(xj, yj) の間の距離は
  √
         (xi −xj)2 + (yi −yj)2 である.)

   4. 上に述べた以外の経路でインフルエンザの流行が拡大することはない.

 また,各i = 1, . . . , n に対し,都市Pi からの距離がd 以下であるようなPi 以外の都市の数は

10 個以下である.

 ある日,インフルエンザの流行が,JOI 市P1 で始まった.JOI 市以外の都市では,今年は,

まだインフルエンザは流行していない.JOI 国では,治療に必要なワクチンを効率よく手配す

るため,インフルエンザの流行状況を予測することにした.

 入力として,都市の数n,1 つの都市でインフルエンザの流行が続く日数m,インフルエンザ

の感染可能距離d,整数k ≥1,各都市の座標が与えられたとき,JOI 市で流行が始まってから

k 日後において,JOI 国内でインフルエンザが流行している都市の数を求めるプログラムを作成

せよ.

                    インフルエンザ–1/3

Input. 入力ファイルflu.in の1 行目には,JOI 国の都市の数n (1 ≦n ≦100, 000) が書か

れている.2 行目には,各都市で流行が続く日数m (1 ≦m ≦100) が書かれている.3 行目に

は感染可能距離d (1 ≦d ≦25) が書かれている.4 行目には整数k (1 ≦k ≦100) が書かれて

いる.続くn 行(5 行目~n + 4 行目) は都市P1, . . . , Pn の位置を表す.i + 4 行目(1 ≦i ≦n) に

は,2 つの整数xi, yi (0 ≦xi, yi < 1, 000) が空白を区切りとして書かれており,都市Pi の座標

がPi(xi, yi) であることを意味する.


Output. 出力は,標準出力に行うこと.JOI 市で流行が始まってからk 日後において,JOI 国

内でインフルエンザが流行している都市の数を表す整数を1 行で出力せよ.

採点基準採点に用いる入力データのうち,配点の20%分はn ≦1000, k ≦50, 0 ≦xi, yi < 100

をみたす.また,これとは別の配点の30%分はn ≦10000, 0 ≦xi, yi < 1000 をみたす.


例
 flu.in 標準出力
 9       4
 2
 2
 3
 1 3
 3 3
 2 2
 3 1
 0 0
 0 3
 0 5
 3 5
 5 5


 この入力例において,都市の数はn = 9 である.また,9 つの都市P1, . . . , P9 の座標は順に

      P1(1, 3), P2(3, 3), P3(2, 2), P4(3, 1), P5(0, 0), P6(0, 3), P7(0, 5), P8(3, 5), P9(5, 5)


で与えられる.インフルエンザの感染可能距離はd = 2 であり,各都市で流行が続く日数は

m = 2 である.また,k = 3 である.





                    インフルエンザ–2/3

y



                          P7             P8        P9



                          P6   P1        P2

                                    P3

                                         P4

                          P5
                                                      x



 最初,インフルエンザが流行しているのはJOI 市P1 のみである.1 日後には,インフルエン

ザの流行は,P1 からの距離が2 以下の都市P2, P3, P6 に拡大する.また,JOI 市P1 における

流行はまだ収まらない.2 日後には,流行はP4, P7, P8 に拡大し,JOI 市P1 における流行は収

まる.3 日後には,流行はP9 に拡大し,P2, P3, P6 における流行は収まる.

 したがって,JOI 市で流行が始まってから3 日後において,インフルエンザが流行している

都市はP4, P7, P8, P9 の4 つであるから,4 を出力すればよい.

 この入力例では,都市P5 においてインフルエンザが流行することはない.





                    インフルエンザ–3/3