Squares(2)

TrisGさんのアイデアを採用しつつ、バイナリサーチの変わりに巨大テーブルを使う方法でかなり高速化できた。

short s[2000];

int o,q,p,r,m,n;
//テーブル

//インプットの上限は20000だが、負の値もいくつか

//含まれるようなので5000ほど底上げしとく

char l[25000][25000];
f(int*a,int*b){return*a-*b;}
g(x,y){

    return x%2|y%2?0:l[x/2+5000][y/2+5000];

}
main(i,j){

    for(;scanf("%d",&n),n;printf("%d\n",m)){

        for(m=i=0;i<n*2;++i){

            scanf("%d",s+i);

            if(i%2){l[s[i-1]+5000][s[i]+5000]=1;}

        }

        for(i=!qsort(s,n,4,f);i<n*2;i+=2)

            for(o=s[i],p=s[j=i+1];++j<n*2;){

                q=s[j],r=s[++j];

                if(o>q||p>=r)continue;//TrisGさん案

                m+=g(o+q-p+r,o-q+p+r)&&g(o+q+p-r,-o+q+p+r);

            }

        for(i=0;i<n*2;++i){//memsetだと時間がかかるから手動で^^;

            if(i%2){l[s[i-1]+5000][s[i]+5000]=0;}

        }

    }

}

しかし、すんごいメモリ消費(;´д｀)

追記：
さらに高速化(TrisGさんのアイデア＋自前クイックソート)で1位ゲッツ(｀ω´)