2002でレッツゴー。
さてと、id:Ozy:20060522経由で知ったこの問題を解いてみましょう。
問題は単純で4点を結んで正方形を作れる数を求める問題です
あ、当然のようにネタばれ注意
まず、Ozyさんの出したアイデアをそのまま採用しましょう。
(1)格子点のうち2つを選んで、それを対角線とする正方形の残り2座標を計算する。 (2)その2座標が、インプットの座標と一致すればカウント。 (3)ただしこの方法だと同じ座標を2回計算することになるので、最後は2で割る。
実はここで(1)を求めるのには三角関数は不要です。
2点をA,Bとして複素数であらわした時、残りの点C,Dは以下のように求められます。
C = A + (B-A)(1+i)/2;
D = A + (B-A)(1-i)/2;
(2)は配列を適当にソートして2分探索で十分でしょう。
より高速化が必要ならハッシュを使うのも手ですが標準ライブラリにはハッシュはありません。
さてと、材料は揃ったので後はコードに直すだけです。
まずは読みやすくC++で高級に書きましょう。
#include#include #include #include typedef std::complex point; struct Cmp{ int operator()(const point&a,const point&b)const{ return a.real() < b.real() || a.real()==b.real() && a.imag() < b.imag(); } }; int main(){ int n; std::vector input; while(std::cin >> n,n != 0){ input.resize(n); for(int i=0;i<n;++i){ int re,im; std::cin >> re >> im; input[i] = point(re,im); } sort(input.begin(),input.end(),Cmp()); int count = 0; for(int i=0;i<n;++i) for(int j=i+1;j<n;++j){ point c = (input[j] - input[i])*point(1,1); //2で割り切れないときはパス if(c.real()%2 !=0 || c.imag()%2 != 0) continue; c = input[i] + c / 2; //見つからないからパス if(!binary_search( input.begin(), input.end(), c,Cmp()))continue; point d = (input[j] - input[i])*point(1,-1); //2で割り切れないときはパス if(d.real()%2 !=0 || d.imag()%2 != 0) continue; d = input[i] + d / 2; //見つからないからパス if(!binary_search( input.begin(), input.end(), d,Cmp()))continue; //見つかったからカウント追加 ++count; } std::cout << count / 2 << std::endl; } }