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

ソートを自前で実装したので長くなってます。

import std.stdio;
import std.math;

void main(){
    uint n = 1000;
    uint r = cast(uint)ceil(sqrt(n / 2.0));
    int[][] gridPoints = [[0, 0]];

    for(uint y; y <= r; y++){
        for(uint x = 1; (x * x + y * y) <= r * r; x++){
            gridPoints ~= [[x, y], [-y, x], [-x, -y], [y, -x]];
        }
    }

    gridPoints.qsort();

    foreach(e; gridPoints){
        writefln(e);
    }

    writefln(n, ": ", gridPoints[n - 1]);
}

void qsort(int[][] array){
    if(array.length < 2) return;

    void swap(uint i, uint j){
        int[] tmp = array[i].dup;
        array[i] = array[j].dup;
        array[j] = tmp;
    }
    int cmp(int[] a, int[] b){
        if(squareDistance(a) == squareDistance(b)){
            real arctanDiff = arctan(a) - arctan(b);
            if(arctanDiff > 0) return 1;
            else if(arctanDiff < 0) return -1;
        }
        else{
            return squareDistance(a) - squareDistance(b);
        }
        return 0;
    }

    uint left = 0;
    uint right = array.length - 1;
    while(true){
        while(cmp(array[left], array[0]) < 0) left++;
        while(cmp(array[0], array[right]) < 0) right--;
        if(right <= left) break;
        swap(left++, right--);
    }
    qsort(array[0..left]);
    qsort(array[(right + 1)..length]);
}

int squareDistance(int[] grid){
    return grid[0] * grid[0] + grid[1] * grid[1];
}

real arctan(int[] grid){
    real arctan = atan2(grid[1], grid[0]);
    if(arctan < 0) arctan += PI * 2;
    return arctan;
}

DouKaku?

格子点の列挙

Posted feedbacks - D

Index

Feed

Other

Link

Pathtraq