2003/Contest/世界大会

Problem H : Tree-Lined Streets

問題概要

いくつかの道路(線分)が与えられる。その道路に次の規則で木を植えるときに、植えられる木の本数の最大値を求める。

  • 隣接する木との間に最低でも 50m の間隔を設ける。
  • 交差点の周囲 25m の範囲には木を植えない。

解法

すべての交差点を求めて道路をいくつかの区間に分割し、各区間に対して植えられる木の本数を計算するだけ。各区間に植えられる木の本数は次の手順で容易に計算可能。

  • 区間の長さを計算する。
  • 両端が交差点の場合は長さから 50m を引く。一端が交差点の場合は 25m を引く。
  • 残りの長さを L とすると、求める木の本数は [L/50]+1(ただし [x] は x を超えない最大の整数)

議論・その他

  • 交点の座標を出すのが少々面倒なくらいで、今回の問題の中でもっとも易しい。一応は実数を扱うのでその取り扱いには注意すること。[泉]

ファイルを添付する

[添付ファイル一覧] [全ページの添付ファイル一覧]
アップロード可能最大ファイルサイズは 10,240KB です。

管理者パスワード:

Last-modified: 2009-11-06 (金) 13:26:46 (3320d)