← 返回题目列表

AtCoder · joisc2009_starry_sky

starry_sky. 星空

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

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

星空 (Starry Sky) - 原题 PDF 第 1 页
原始 PDF 第 4 部分
星空 (Starry Sky) - 原题 PDF 第 2 页
原题PDF第5页
可复制的 PDF 提取文本
Starry Sky: 星空


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



  JOI(Japan Observatory Institution:日本天文台協会) は,最近,高性能な天体望遠鏡を設置し

た.JOI は,この天体望遠鏡の性能を広く一般にアピールすることで,JOI の知名度向上につ

なげようと考えている.長い会議の結果,この天体望遠鏡の性能をアピールするもっとも効果

的な宣伝方法は,十分に輝いている星ができる限り沢山映った画像を撮影し,広く一般に公開

することであるという結論に至った.

 しかし,宇宙は広大である.1 枚の画像の中に全てを収めようとすれば,一つ一つの星の輝き

を十分に表すことができない.

 一方,この天体望遠鏡は高性能である.拡大して星空を撮影することで,各星が十分に輝い

た状態として撮影することができる.ただし,拡大することで,画像の中に収めることができ

る星の数が減ってしまう.最大で,いくつの十分に輝く星を画像の中に収めることができるだ

ろうか.

 各星に関する次の情報が与えられたときに,十分に輝いた星として画像の中に収めることが

できる星の最大数を求めるプログラムを作成せよ.


   • 星の位置は,x 座標とy 座標からなる2 次元座標として与えられる.

   • この天体望遠鏡で撮影できる画像は,各辺がx 軸かy 軸に平行な任意の大きさの正方形で

   ある.星の光度と十分に輝いた状態になるまでに必要な拡大倍率の関係を表すために,星

   毎に,十分に輝いた状態で撮影するために必要となる正方形領域の一辺の長さL が与え

   られる.撮影する正方形領域の一辺の長さがL 以下でなければ,画像の中にその星が入っ

   ていたとしても十分に輝いた星として撮影することができない.正方形領域の辺上に星が

   あったとしても,十分に輝いている状態の星であれば,その星は画像の中に入っていると

   して数えることに注意せよ.


 ただし,どの異なった2 つの星も,互いのx 座標,互いのy 座標,互いのL の値のどれも一

致することが無い.

Input. 入力ファイルstarry sky.in の1 行目には,星の数を表す整数N(1 ≦N ≦4000) が

書かれている.

                            星空–1/2

続くN 行は星のデータを表す.i + 1 行目(1 ≦i ≦N) には3 つの整数xi, yi, Li(0 ≦xi ≦
109, 0 ≦yi ≦109, 1 ≦Li ≦109) が空白を区切りとして書かれている.これは,星のx 座標,y

座標,十分に輝いている状態として撮影できる正方形領域の一辺の長さの最大値を表す.


Output. 出力は,標準出力に行うこと.十分に輝いている状態として撮影できる星の数の最

大数を表す整数を,1 行で出力せよ.

採点基準採点用データのうち,配点の15% 分についてはN ≦100,配点の25% 分については

N ≦400,配点の35% 分についてはN ≦700,配点の50% 分についてはN ≦1000 を満たす.

また,配点の20% 分についてはxi, yi, Li ≦1000 を満たす.

例1             例2
 starry sky.in 標準出力    starry sky.in 標準出力
 4              3          5              2
 1 2 6                     11 6 7
 4 3 3                     12 13 8
 3 1 4                     15 16 18
 5 5 2                     2 2 13
                           3 4 11





                            星空–2/2