PKU : 3432 - Count Squares

幾何

問題概要

http://poj.org/problem?id=3432

二次元平面上にN個の点が与えられます.
この中から４つの点を選択したとき, 正方形になるような選び方は何通りあるか答える問題.

アルゴリズム

N=2000なので, ４乗解法では通らないでしょう.
ある二点を選んだとき, 正方形になるような位置に残りの２点があるかを調べましょう.
これで２乗解法になって通ります.
AOJの0518は, 全く同じ問題だったはず.

プログラム

typedef pair<int,int> P;

int main(void){
  int n;
  int x[2000],y[2000];

  while(scanf("%d",&n) != EOF){
    int ans = 0;
    set<P> s;

    rep(i,n){
      s.insert(P(x[i],y[i]));
    }

    //点を昇順に並び変え
    int idx = 0;
    foreach(i,s){
      x[idx] = i->first;
      y[idx] = i->second;
      idx++;
    }

    rep(i,n){
      REP(j,i+1,n){
        int diffX = x[j] - x[i];
        int diffY = y[j] - y[i];
        P a(x[i]+diffY,y[i]-diffX);
        P b(x[j]+diffY,y[j]-diffX);

        if(s.find(a)!=s.end() && s.find(b)!=s.end()){
          ans++;
        }
      }
    }
    printf("%d\n",ans/2);
  }
}