二次元平面状の原点に駅があり、その駅を始端として半直線状に地下鉄の線路を通す。
線路の上には好きなだけ駅を作って良い。
主要都市が格子点上にN点(1<=N<=500)存在し、これらの都市は、最も近い駅から距離d(0<=d<150)以内に無ければいけないと規定されている。
最低でも何本地下鉄を通す必要があるか?

まず、原点の駅がカバーする都市は無意味なので全て取り除く。
残りの各都市が、地下鉄をこの角度からこの角度の間に1本作らなくてはならないという制約になっているのはすぐ気づく筈だ。
もし、どの都市の条件にも含まれない角度が存在するなら、問題は区間グラフの問題となる。
区間グラフの問題ならば、
「この角度までに1本引かなくてはいけない、という所に1本引く => その地下鉄のカバーする都市を取り除く => はじめに戻る」
というアルゴリズムを用い、O(n^2)で最小本数を求めることができる。
しかし、この問題ではそのような角度が存在する事は保障されておらず、区間グラフの始めと最後がくっついた形になっている為、そのままではこのアルゴリズムが使えない。
そこで、適当に地下鉄を一本通してしまい、その地下鉄がカバーする都市を取り除いてしまう事でループを切り開き、このアルゴリズムを適用できるようにしてしまう事を考える。
全区間の右端、左端での切り開きを試してしまえば、少なくともどれかは、最小線路数を達成できる線路の敷き方の一部になっているだろう。

計算量は、切り開く点O(n) * 区間グラフアルゴリズムO(n^2)のO(n^3)となる。

3004.cpp