51. 今日は頭が寝ている日
今日はいまいち調子が悪く、あんまり進捗ありませんでした。
とりあえず、昨日積み残していた競プロ典型90問の問9をACしました。
この問題は全探索による解法は浮かんで、でも だから無理だなぁ、と思いました。ただ、とりあえず書けることが大事だとも思ったので、思うように書いてみてTLEは出せました。
制約的に、おそらく三重ループの最後を対数時間に落とせれば全体として になって通るなぁ、と考えました。2点は全探索で良いので、注目している1点から引ける線分のうち、注目している線分(ベクトル)と正反対に近いものを対数時間で見つけられれば良いんだけどなぁ…と思いながら、方法が分からず解説を読みました。なるほど、考え方は合っていた感じでした。
というわけで、偏角についての二分探索をライブラリに書いて、無事通しました。
次の問題はセグメント木っぽいなぁ…と思いつつ、これもライブラリに追加するところからですね…。また明日。