SRM362 Div1 250

問題

N点を平面におくことができる．(点を結んだ線分が軸に平行な)異なる正方形は最大いくつつくれるか．

考え方

どのように点を配置していった場合，正方形が多く作れるかを考える．
点の数が4,9,16,25,...の時はそれぞれ2*2,3*3,4*4,5*5,...の(その中を点で埋め尽くしている)正方形になるようにすると正方形の数が多くなることがわかる．なので，N点で，なるべく大きな(その中を点で埋め尽くしている)正方形を作り，残りの点でその正方形の横に付け足すように配置すればよい．あとは，それぞれの正方形の個数を計算すればいい．