AOJ2015:Square Route

幾何（大嘘）

問題↓

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2015

問題概要

• N本の縦線とM本の横線が与えられます
• それぞれの直線と直線の間の幅が与えられます
• 線を囲んでできる正方形はいくつあるでしょう

解法

• 縦線と横線に対して別々に累積和を取る
• 何本間隔で見るか(J)を決め打ちして、(i,i+J)の区間の幅を得てカウントする
• 縦線における幅jの数　✕　横線における幅jの数 の合計が答え

ソースコード

感想

他に簡単な解法があれば無理して幾何する必要はない（というかこの場合、幾何ゲーするほうがむずい気がする）