← 返回题目列表

AtCoder · joisc2008_cheating

cheating. 针对作弊的对策(作弊)

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

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

カンニング対策 (Cheating) - 原题 PDF 第 1 页
原题PDF第3页
カンニング対策 (Cheating) - 原题 PDF 第 2 页
原题PDF第4页
可复制的 PDF 提取文本
Cheating: カンニング対策


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



 近年,日本情報オリンピックは受験者数が著しく増加したが,それにつれて不正行為を行う

受験者も増えてしまい,問題となっている.日本情報オリンピックの試験会場は長方形である.

座標軸をそれぞれ試験会場の壁に平行にとり,原点は試験会場の一つの隅とする.

 情報オリンピック日本委員会は受験者の不正行為を自動で監視する装置をn 個製作した.そ

れぞれの監視装置は,x 軸方向の監視またはy 軸方向の監視のいずれかに用いることができる.


   • 監視装置i をx 軸方向の監視に用いるとき,監視装置i はpi ≦y ≦pi + di の領域にいる

   受験者を監視する.

   • 監視装置i をy 軸方向の監視に用いるとき,監視装置i はpi ≦x ≦pi + di の領域にいる

   受験者を監視する.


 ただし,di, pi の値は整数であり,それぞれの監視装置について個別に設定できるが,0 ≦di

で,di が小さいほど精度よく監視することができる.使用しない監視装置があってもよい.





                 図1: 監視装置で受験者を監視している様子


 情報オリンピック日本委員会は,注意を要する受験者のリストを持っており,それらの受験

者をできるだけ精度よく監視しようと考えた.したがって,図1 のように,各々の受験者に対

してx 軸方向に監視を行っている監視装置1 つ以上と,y 軸方向に監視を行っている監視装置1

つ以上により要注意の受験者を監視しなければならない.さらに,全ての監視装置でのdi の最

大値をdmax としたとき,dmax をできるだけ小さくしなければならない.


                    カンニング対策–1/2

善良な受験者であるあなたに,監視装置の個数n と要注意の受験者の座標が与えられたとき,

dmax の最小値を出力するプログラムの作成を依頼する.ただし,受験者は動かないものとし,

監視装置に監視される領域の境界に受験者がいるとき,その受験者は監視されているものとす

る.また,受験者の座標は全て異なる.

Input.  入力ファイルcheating.in の1 行目には,2 つの整数n, m (2 ≦n ≦200, 000,

1 ≦m ≦100, 000) が空白を区切りとして書かれている.これは,製作した監視装置の個数がn

個,要注意の受験者の人数がm 人であることを表す.

 続くm 行(2 行目からm + 1 行目) は要注意の受験者の座標を表す.j + 1 行目(1 ≦j ≦m)

には,2 つの整数xj, yj(0 ≦xj, yj ≦1, 000, 000, 000) が空白を区切りとして書かれている.これ

は,j 人目の要注意の受験者の座標が(xj, yj) であることを表す.

Output. 出力は,標準出力に行うこと.dmax の最小値を表す1 つの整数を出力せよ.

採点基準採点用データのうち,配点の30% 分については,n, m ≦100 かつ全てのj について

xj, yj ≦10, 000 を満たす.また,配点の別の20% 分については,n, m ≦1000 を満たす.


例
 cheating.in 標準出力
 4 5          3
 4 9
 2 4
 7 8
 6 1
 4 4





                    カンニング対策–2/2