AOJ : 0518 - 最古の遺跡 (The Oldest Site)

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0518&lang=jp
問題文が日本語なので省略です

アルゴリズム

単純に四重ループで四角形の4点を決めて、正方形かどうか判断する方法では、O(n^4)となって、TLEになることが予想できます。
そのため、次のようにO(n^2)のアルゴリズムにすれば、通せます。

二重ループによって、点の集合からある2点A,Bを選択する。
線分ABの単位法線ベクトル V を出す。
次の2つの条件が成り立つなら4へ、そうでないなら1へ戻る。
- 点Aから単位法線ベクトルVを線分ABの距離の長さ分伸ばした位置に点がある(これを点Cとする)
- 点Bから単位法線ベクトルVを線分ABの距離の長さ分伸ばした位置に点がある(これを点Dとする)
正方形ABDCの面積を求め、最大面積より大きいなら更新する。

ただし、点CやDの点があるかどうか検索するとき、セットなどで管理している場合、検索に時間がかかってしまいます。
そのため、O(1)でヒットするように、2次元配列で管理します。
この際、int型にするとMLEになるため、char型にする必要があります。

プログラム

#include <iostream>
#include <complex>
#include <vector>
#include <cstring>
using namespace std;

#define REP(i,n,m) for(int i=n;i<m;i++)
#define rep(i,n) REP(i,0,n)

typedef complex<double> P;

P p[3001];
char flg[5001][5001]; //[x][y]が 1 : (x,y)の点がある, 0 : (x,y)の点がない

//外積
double cross(P a,P b){
  return (a.real() * b.imag() - a.imag() * b.real());
}

//面積
double area(vector<P> v){
  int n = v.size();
  double res = 0.0;
  rep(i,n) res += cross(v[i],v[(i+1)%n]);
  return fabs(res/2);
}

int main(void){
  int n;

  while(cin>>n,n){
    memset(flg,0,sizeof(flg));

    rep(i,n){
      int x,y;
      cin>>x>>y;
      p[i] = P(x,y);
      flg[x][y] = 1;
    }

    double ans = 0.0;

    //2点どれかを選ぶ
    rep(i,n) REP(j,i+1,n) {
      P ab = p[i] - p[j];
      P un = (ab * P(0, +1)) / abs(ab); //abの単位法線ベクトル
      P c = p[i] + un * abs(ab);
      P d = p[j] + un * abs(ab);

      if(c.real() - (int)c.real() != 0.0 ||
         c.imag() - (int)c.imag() != 0.0 ||
         d.real() - (int)d.real() != 0.0 ||
         d.imag() - (int)d.imag() != 0.0 ||
         c.real() < 0 || c.imag() < 0 ||
         d.real() < 0 || d.imag() < 0 ||
         c.real() > 5000 || c.imag() > 5000 ||
         d.real() > 5000 || d.imag() > 5000) continue;

      //点c,dが存在するなら正方形がある
      if(flg[(int)c.real()][(int)c.imag()] && flg[(int)d.real()][(int)d.imag()]){
        vector<P> v;
        v.push_back(p[i]);
        v.push_back(p[j]);
        v.push_back(d);
        v.push_back(c);
        double cal = area(v);
        if(ans < cal) ans = cal;
      }
    }

    cout<<(int)ans<<endl;
  }

  return 0;
}