格子点の列挙 in Other 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 - Other

多めに取っておく
（1000個の格子点は半径18以内にある）

        [,1] [,2]      [,3]
   [1,]    0    0  0.000000
   [2,]   -1    0  1.000000
   [3,]    0   -1  1.000000
   [4,]    0    1  1.000000
   [5,]    1    0  1.000000
   [6,]   -1   -1  1.414214
   [7,]   -1    1  1.414214
   [8,]    1   -1  1.414214
   [9,]    1    1  1.414214
  [10,]   -2    0  2.000000
中略 
 [995,]   11   14 17.804494
 [996,]   14  -11 17.804494
 [997,]   14   11 17.804494
 [998,]  -16   -8 17.888544
 [999,]  -16    8 17.888544
[1000,]   -8  -16 17.888544

1
2
3

d <- outer(-25:25, -25:25, function(i, j) sqrt(i^2+j^2))
o <- order(d)
cbind(rep(-25:25, each=51)[o], rep(-25:25, 51)[o], d[o])[1:1000,]

DouKaku?

格子点の列挙

Posted feedbacks - Other

Index

Feed

Other

Link

Pathtraq