AOJ2015:Square Route
幾何(大嘘)
問題↓
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2015
問題概要
- N本の縦線とM本の横線が与えられます
- それぞれの直線と直線の間の幅が与えられます
- 線を囲んでできる正方形はいくつあるでしょう
解法
- 縦線と横線に対して別々に累積和を取る
- 何本間隔で見るか(J)を決め打ちして、(i,i+J)の区間の幅を得てカウントする
- 縦線における幅jの数 ✕ 横線における幅jの数 の合計が答え
ソースコード
感想
他に簡単な解法があれば無理して幾何する必要はない(というかこの場合、幾何ゲーするほうがむずい気がする)