← 返回题目列表

AtCoder · joisc2010_sengoku

sengoku. 战国时期(战国)

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

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

戦国時代 (Sengoku) - 原题 PDF 第 1 页
原题PDF第3页
戦国時代 (Sengoku) - 原题 PDF 第 2 页
原始 PDF 第 4 部分
可复制的 PDF 提取文本
Japanese Olympiad In Informatics 2009/2010
                                                                          Spring Training Camp
                                              March 19 - 25, 2010, Komaba/Yoyogi, Tokyo

                                                                           Contest day 1 - Sengoku

                    戦国時代(Sengoku)


 時は戦国時代のまっただ中.JOI 国を率いるJOI 武将は,来たるべき戦いに備え,自らの領地に見張りを
配備することになった.
  JOI 国の領地は,東西幅、南北幅がL の正方形の形をしている.領地は1 × 1 の正方形の区画に分かれて
おり,各区画は0 ≦x < L, 0 ≦y < L を満たす整数x, y によって(x, y) と表現される.区画(0, 0) は北西隅の
区画であり,区画(x, y) は,区画(0, 0) から東にx,南にy 進んだ地点に位置する区画である.
 それぞれの見張りは領地内のある区画にとどまり,次のような範囲を見張る.(x, y) の位置にいる見張り
は,条件|x −i| = |y −j| をみたす領地内の区画(i, j) 全体を見張る(この範囲は,他の見張りの位置によって
変化することはない).なお,同一の区画に2 人以上の見張りがいるということはない.

課題(TASK)
  JOI 武将が配備したN 人の見張りの場所が与えられると,少なくとも1 人以上の見張りに見張られてい
る領地内の区画の個数を求めるプログラムを作成せよ.

制限(CONSTRAINTS)
   1 ≦L ≦100, 000, 000 領地の1 辺の長さ
   1 ≦N ≦100, 000   見張りの数

入力(INPUT)

 標準入力から以下の入力を読み込め.

   • 1 行目には整数L とN が空白を区切りとして書かれている.

   • 続くN 行は,1 行につき1 人の見張りについて記述している.これらの行のうちのi 行目はi 番目の
   見張りについて記述しており,整数xi とyi (0 ≦xi < L, 0 ≦yi < L) が空白を区切りとして書かれて
   いる.

出力(OUTPUT)

 標準出力に以下のデータを出力せよ.

   • 1 行目には,1 人以上の見張りによって見張られている区画の個数を表す,1 つの整数が含まれてい
   なければならない.




                                                                                    Page 1 of 2

Japanese Olympiad In Informatics 2009/2010
                                                                          Spring Training Camp
                                              March 19 - 25, 2010, Komaba/Yoyogi, Tokyo

                                                                           Contest day 1 - Sengoku

採点基準(GRADING)
  15 点分のテストグループにおいて,L, N は1, 000 を超えない.また,40 点分のテストグループにおい
て,N は1, 000 を超えない.

入出力例(EXAMPLE)
  入力例(Sample Input)  出力例(Sample Output)
   5 4                 18
   4 1
   1 1
   1 0
   3 3

 このときのJOI 国を図示すると,下のようになる.見張られている区画の個数は18 である(黒丸は見張
りを表す.また,見張られている区画は灰色で示されている).





                                                                                    Page 2 of 2