格子点の列挙 in Common Lisp DouKaku?

格子点の列挙

二次元平面上の格子点(X,Y座標がともに整数の点)を、原点から近い順に列挙してください。

同じ距離の点はどういう順番でも構いませんが、可能であればX軸に一番近い第一象限の点から原点を中心として反時計回りの順に列挙してください。列挙の方法は、1行に一つの点の、X,Y座標を出力することとします。

サンプル出力

0, 0
1, 0
0, 1
-1, 0
0, -1
1, 1
-1, 1
1, -1
-1, -1
2, 0

最低でも1000件まで列挙できることを確認してください。また「反時計回り」の条件も満たしている場合は、1000番目の頂点が何かも併せて答えてください。

このお題はかもさんの投稿を元にしています。ご協力ありがとうございました。

Perl がなかったので。力技。

use strict;

my $PI = atan2(1, 1) * 4;
my $MAXR = int(sqrt(1000 / $PI) + sqrt(2) + 0.5);
my @res = ();

for (my $i = 0; $i <= $MAXR; $i++) {
    for (my $j = 0; $j <= $MAXR; $j++) {
        my $r = sqrt($i * $i + $j * $j);
        push(@res, [$i, $j, $r, atan2($j, $i)]);
        ($i != 0) && push(@res, [-$i, $j, $r, atan2($j, -$i)]);
        ($j != 0) && push(@res, [$i, -$j, $r, atan2(-$j, $i) + 2 * $PI]);
        ($i * $j != 0) && push(@res, [-$i, -$j, $r, atan2(-$j, -$i) + 2 * $PI]);
    }
}

foreach my $p (sort {($a->[2] <=> $b->[2]) || ($a->[3] <=> $b->[3])} @res) {
    printf("%3d, %3d\n", splice(@{$p}, 0, 2));
}

post comment

Posted feedbacks - Common Lisp

格子点のリストを適当に生成しておいて、
原点からの距離でソートすることで近い順に並べてます。
反時計回りにはなってません。

(defun distance (point)
  (let ((x (first point)) (y (second point)))
    (+ (* x x) (* y y))))

(defun list-lattice-points (n)
    (loop with a = (ceiling (sqrt (/ n 2)))
      for i from (- a) to a
      nconc (loop for j from (- a) to a collect (list i j)) into points
      finally (format t "~V{~{~D, ~D~}~%~}"
                      n (sort points #'<= :key #'distance))))

探索範囲を狭めました。
ついでに反時計回りになるようにしました。

評価の方法ですが、
円内の格子点に正方形を対応させると円の被覆ができるので、
これを使って格子点の数を円の面積で見積もるというのが大まかな方針です。

細かい計算は以下。
軸の周りで一対一対応にならなくてややこしいことになってます。

C: 原点を中心とする半径 r の閉円板
f: 単位正方形に対し、その頂点のうち最も原点に近いものを対応させる写像

C に属する格子点の数を K とすると、
f による像が C に入っているような単位正方形の数は
 原点に写るものが 4 個
 原点以外で軸上に写るものが 8r 個
 それ以外の点に写るものが K-4r-1 個
合わせて K+4r+3 個となります。
これらの単位正方形の和集合を S とします。

C は S の部分集合なので、S の面積は C の面積以上になります。
S は K+4r+3 個の単位正方形からなるので、その面積は K+4r+3 です。
また C の面積は pi*r^2 なので
pi*r^2 <= K + 4r + 3
が得られます。K が格子点の数だったので、格子点は少なくとも
pi*r^2 - 4r -3 個以上あることがわかります。

というわけで、格子点の数が n 以上となる半径 r を見つけるには
pi*r^2 - 4r - 3 >= n
を解けばよく、その結果
r >= (sqrt(4 + (3 + n) * pi) + 2) / pi
となります。

(defun point< (p1 p2)
  (destructuring-bind ((x1 y1) (x2 y2)) `(,p1 ,p2)
     (let ((a1 (+ (* x1 x1) (* y1 y1)))
           (a2 (+ (* x2 x2) (* y2 y2))))
       (or (< a1 a2)
           (and (= a1 a2)
                (if (>= y1 0)
                    (or (> 0 y2) (> x1 x2))
                  (and (> 0 y2) (< x1 x2))))))))

(defun list-lattice-points (n)
  (loop with a = (ceiling (/ (+ (sqrt (+ 4 (* (+ 3 n) pi))) 2) pi))
    for i from (- a) to a
    nconc (loop with b = (floor (sqrt (- (* a a) (* i i))))
            for j from (- b) to b collect (list i j)) into points
    finally (format t "~V{~{~D, ~D~}~%~}"
                    n (sort points #'point<))))

DouKaku?

格子点の列挙

Posted feedbacks - Common Lisp

Index

Feed

Other

Link

Pathtraq