CS Academy Round #76 - Pyramids

• 問題
• AC

ある種の区分線形関数に囲まれた領域の格子点を数える問題。区分線形関数を構成する線分の総数が${\mathcal O}(N)$なので、全部列挙して線分毎に下にある格子点を数えればよさそう。

まずは、与えられた点で折れ線を構成するものだけを左から列挙したい。点を$c$の昇順でソートしてスタックを持ちながら走査する。ある点$(r, c)$による山を処理するとき、スタックの先頭に入っている点（=ひとつ前の山の頂上）による山との関係には次の3通りがある:

1. 前の山に完全に含まれる
2. 前の山を完全に含む
3. 前の山と一部重なるか、遠く離れていて重ならない

今見ている点を$(r, c)$、スタックの先頭に入っている点を$(r', c')$として、

• $c+r \le c' + r'$なら1、つまり前の山に含まれるので無視
• $c-r \le c'-r'$なら2、つまり前の山を含むのでスタックをポップしてさらに前の点を見る
• それ以外は3なので新しい点をスタックにプッシュする

こうするとスタック（の反転）には山の頂点として有効な点だけが左から並ぶので、その間にできる谷に関する格子点をそれぞれ数えればよい。

数え上げパートについて。山の頂点が左から$(r_1, c_1), ..., (r_k, c_k)$と並んでいるとする。頂点$(r_i, c_i)$と$(r_{i+1}, c_{i+1})$の間にできる谷は直線$y=-(x-c_i)+r_i$と直線$y=x-c_{i+1}+r_{i+1}$の交点であり、その$y$座標は$(r_i+r_{i+1}+c_i-c_{i+1})/2$と表せる。そこで、$H= \max(0, \lceil (r_i+r_{i+1}+c_i-c_{i+1})/2 \rceil)$としてまずは下部の長方形の格子点を$H(c_{i+1}-c_i+1)$と数え、さらに上部の三角形の格子点を$(r_i-H)^2 + (r_{i+1}-H)^2$と数える。また、左端の頂点$(r_1, c_1)$の山の左側半分にある格子点$r_1^2$個と右端の頂点$(r_k, c_k)$の山の右側半分にある格子点$r_k^2$個は別に加算する。このとき、各頂点の下にある格子点をちょうど2回ずつ数えているので、$\sum_i r_i$を引けば正しい数になる。