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

なんか旨い方法はないかと思っていたのですが、結局、普通の方法になってしまいました。その代わり反時計回りの条件を満たしています。

1000個目は
-8, 16
です。

ちなみに、最初の10個（反時計回り）は
0, 0
1, 0
0, 1
-1, 0
0, -1
1, 1
-1, 1
-1, -1
1, -1
2, 0
になります。

import java.util.*;

public class Sample {
    public static void main(String[] args) {
        ArrayList<Point> lattice = new ArrayList<Point>();
        for (int x = -20; x <= 20; x++) {
            for (int y = -20; y <= 20; y++) {
                lattice.add(new Point(x, y));
            }
        }
        Collections.sort(lattice);
        int count = 0;
        for (Point p : lattice) {
            System.out.printf("%d, %d%n", p.x, p.y);
            if (++count >= 1000)
                break;
        }
    }
}

class Point implements Comparable<Point> {
    int x, y;
    int abs2;
    double theta;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
        abs2 = x * x + y * y;
        theta = Math.atan2(y, x);
        if (theta < 0) theta += 2*Math.PI;
    }
    public int compareTo(Point p) {
        if (this.abs2 != p.abs2) {
            return this.abs2 - p.abs2;
        } else {
            return Double.compare(this.theta, p.theta);
        }
    }
    public String toString() {
        return "(" + x + ", " + y + "):" + abs2;
    }
}

DouKaku?

格子点の列挙

Posted feedbacks - Java

Index

Feed

Other

Link

Pathtraq