Squares(0)

id:xatm092doraさんがお悩み中のようなので、ちょっと考えてみた。平面座標上にある格子点の中から、正方形を作ることが出来る4点を選ぶ組み合わせを計算する問題。格子点の最大数が1000ということで、O(n^4)がTLEになるのは明らかだ。さっきO(n^3)でちゃちゃっと書いてみたがTLEになったので、もう少しチューニングが必要だろう。私がピコーンと思いついたアルゴリズムは、

①格子点のうち2つを選んで、それを対角線とする正方形の残り2座標を計算する。
②その2座標が、インプットの座標と一致すればカウント。
③ただしこの方法だと同じ座標を2回計算することになるので、最後は2で割る。

方向性としては間違っていないと思う。私が書いたコードは②の部分を線形探索しているのでO(n^3)でもかなり遅いが、探索方法の工夫（特に最悪計算量が少ないものをチョイス）でTLEは避けられるんじゃないかと。

①の計算は、2点のうち1点を原点に来るように平行移動してから三角関数でも使って±45度回転させたあと√2で割ればいいだろう。もっと良い方法があるかな？

まーそんなとこです。

追記：
早速id:kurimuraさんが短いコードを書いてらっしゃる。さっすがー！解説キボンヌ。
http://d.hatena.ne.jp/kurimura/20060523
そのまま実装してくれました。2分探索で間に合うようです。