yukicoder No.1137 Circles - かんプリンの学習記録

問題概要

中心が ${x}$ 軸上にあるような円が ${N}$ 個与えられる. ${xy}$ 平面上の点のある点を内部(円周は内部ではないとする)に持つ円の数の最大値を求めよ.

円の内部とかいう条件が幾何っぽくて扱いづらい. ちょっと考えると以下のようなことに気づける.

ある点 ${(a,b)}$ がある円の内部にあるならば, その点を ${x}$ 軸に投影した点 ${(a,0)}$ もその円の内部にある.

図に表すとこんな感じ, これは直感的にもすぐにわかりそう.

f:id:kanpurin:20200729015240p:plain

ここから ${x}$ 軸の点のみ考えればいいことがわかる. 結局, 円の ${y}$ 軸方向の情報はいらないので ${x}$ 軸上での区間のみ考えればいいことになる.

f:id:kanpurin:20200729015911p:plain

ただし, 区間の端は含まない.

問題は区間が最大いくつ重なってるかを求める典型問題になった. 区間の範囲が ${-10^5}$ から ${10^5}$ と狭いのでimos方を使えば ${O(N+(区間の範囲))}$ で解ける.

区間の範囲が広くなっても座標圧縮をしたりsetを用いればよい. 今回はいらない.

特になし