AtCoder Regular Contest 071 D 井井井 / ###
x軸に平行な直線がm本、y軸に平行な直線n本、あり、それぞれのy座標、x座標はy[i], x[j] である。これらの交点を使って任意の長方形を作る。そういう長方形の面積の総和を求めよ。
x軸とy軸で独立して考える。x[i]からx[i - 1]の間の領域が長方形の面積として使われる回数は、その領域が含まれる長さすべてで、左右の頂点の数を書ければよく、 i * (n - i) 通り。なので、(x[i] - x[i - 1]) * i * (n - i) の総和を求める。
y軸も同様にして総和を求め、x軸の和とかけると答え。
