2003/Contest/世界大会

Problem H : Tree-Lined Streets †

問題概要 †

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

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

解法 †

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

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

議論・その他 †

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

ファイルを添付する †