読者です 読者をやめる 読者になる 読者になる

AOJ2015:Square Route

幾何(大嘘)

問題↓

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

問題概要

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

解法

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

感想

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