AOJ 2015 - Square Route

Square Route | Aizu Online Judge

問題

街がある。その街の道路は端から端まで引かれている。
矩形の辺に道路を使って正方形を作り、その数を数えろ。

考え方

各道路の交点から左上に線を引きその線上に別の交点が存在したときに正方形を作ることができる。
そのためにまず、各交点をX軸状に射影する。

int y = 0, dy;
for(int xx:xs){
	ps[xx-y]++;
}
REP(i, h_n){
	cin >> dy;
	y += dy;
	for(int xx:xs){
		ps[xx-y]++;
	}
}

交点の数(n)が求まったら、Σnで解が求まる(nの値毎に正方形がいくつできるのか数えたらΣnっぽかった)。