AtCoder Beginner Contest 168 F - . (Single Dot)

解法の理解というよりは実装慣れのほうが重要な問題だと思います。末尾につけているACコード例と対応させながら読んでいくといいかもしれません。

解法

図における座標軸は問題文に従い、北を上にして図示するようにします。一般的なXY平面とは異なるので注意してください（プログラミングでグリッド等を扱うときによく使われる取り方です）。

座標平面をグリッドのマスのように考えると、UnionFindで連結判定をしたりグリッド上でBFSをしたりして牛から到達可能なマス数を数える、という解法が思い浮かびます。しかし $1\times 1$ の領域を1つのマスとして扱うには座標の値が大きすぎます。そこで座標圧縮をします。

圧縮座標の取り方は細かい違いを考慮すると色々ありますが、この解説では以下のように取ります。

f:id:betrue12:20200518002554p:plain

それぞれの線分の端点の座標を集めてきてソート＆重複除去を行い、座標圧縮します。ここで実装上は無限に遠い座標（無限遠、十分大きな整数）を正負それぞれ含めておくと楽です。

そしてその座標値で区切られる長方形領域を、その左上の圧縮座標のインデックスと対応付けます。このようにすれば領域の面積が求められて、領域同士の連結判定もUnionFindなどで扱うことができます。

次に線分の扱い方を考えましょう。ここではそれぞれの線分から、各長方形領域について

という情報を求めてしまうと扱いやすくなります（下側/右側でも添字が1つずれるだけなので可能です）。例えば上図の縦線は、領域 $(2, 1)$ と領域 $(3, 1)$ の左側に線分が存在する、という情報にすることができます。

こうしてしまえば、例えばUnionFindを用いて各領域が接しているところについて「間に線分がなければ併合」という処理を行うことで連結判定ができるようになります。牛が存在する領域と連結な領域の面積を合計すれば答えになります。ただし無限遠の座標に対応する領域と連結であれば答えは INF です。

実際に解く時には、手元で図を描いて、ちゃんと座標と領域の対応付けを決めてから実装に落とし込むと良いです。