CS過去問のメモ

2014computer-s1-3(4)
　x座標が最小であるQの要素をq0とする。q0.x - p.x < lpとなるようなPの要素で配列P1を作る。また、q.x - q0.x < lpとなるようなQの要素で配列P2を作る。lpよりも距離が小さくなり得るのはP1とP2の要素の組み合わせであるが、P2に対してP1の要素は高々定数個(6だけど、容易に示せるのはこの問題のように8)であるから、探索/列挙(下記nearestP)はO(6*(n/2))=O(n)で終わる。あとはこの分割を再帰させるだけなので、時間計算量はO(nlog(n))となる。
　Inner loopは、lower boundの維持とbreakによるupper boundによってP2の要素それぞれに対してO(1)で動作する。OuterがO(n)だからO(n)。

float nearestP(Point P1[], Point P2[], float lp) {
  int lb = 0; //P1のlower bound
  bool update; //lbを一度だけupdateするためのflag
  float min_all_q = lp;
  for(int i = 0; i < P2.length; i++) {
    float min = lp;
    int near = 0; //nearest p
    bool update = false;
    for(int j = lb; j < P1.length; j++) { //length=sizeof(P1)/sizeof(*P1)かな？
      //p.y > q.y + lp ならqを次に
      if (P1[j].y - P2[i].y > min) break;
      //p.y > q.y - lp なら距離を出す
      if (P2[i].y - P1[j].y < min) {
        if (dist(P2[i],P1[j]) < min){
          min = dist(P2[i],P1[j]);
          near = j;            
        }
        if (!update) { //下限のupdate
          lb = j;
          update = true;
        }
      }
    }
    if (min < lp) printf("nearest p(%d,%d)\n", P1[near].x, P1[near].y);
    if (min < min_all_q) min_all_q = min;
  }
  return min_all_q;
}

あくまで擬似コードなので動きません、lengthとかPointとかdistとか定義してないし……。