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

個数をコマンドラインパラメータにして、きりのいいところの点のみstderrにも出力するようにしました。

Windows XP + cygwin
800Mhz 512MB
100000個めまでで0.7sくらい
1000000個めまでで10sくらい
10000000個めまでで2m12sくらい

        1: (     0,      0)
       10: (     2,      0)
      100: (    -4,     -4)
     1000: (    -8,     16)
    10000: (   -34,     45)
   100000: (   132,   -120)
  1000000: (   497,   -267)
10000000: (   474,  -1720)

正直なところ、間違ってないかすごく怖いので、だれか他の人もやってみてほしいです。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define PI 3.14159265358979

typedef struct{
    int x;
    int y;
    int len2;
    double theta;
} POINT;

POINT *points;
POINT **pPoints;

int compair(const void *_a, const void *_b){
    POINT *a = *(POINT **)_a;
    POINT *b = *(POINT **)_b;
    if(a->len2 != b->len2)
        return a->len2 - b->len2;
    else
        return a->theta < b->theta ? -1 : 1;
}

int main(int argc, char *argv[]){
    int n, max, size, ind, i, j;
    if(argc < 2)
        return 1;
    n = atoi(argv[1]);
    for(i=1; ; i++){
        if(i * i * 3 > n)
            break;
    }
    max = i;
    size = (max*2+1) * (max*2+1);
    points = (POINT *)malloc(sizeof(POINT) * size);
    pPoints = (POINT **)malloc(sizeof(POINT *) * size);
    ind = 0;
    for(i=-max; i<=max; i++){
        for(j=-max; j<=max; j++){
            points[ind].x = i;
            points[ind].y = j;
            points[ind].len2 = i*i + j*j;
            points[ind].theta = (i==0 && j==0) ? 0 : atan2(j, i);
            points[ind].theta += points[ind].theta < 0 ? 2 * PI : 0;
            pPoints[ind] = &points[ind];
            ind++;
        }
    }
    qsort(pPoints, size, sizeof(POINT *), &compair);
    for(i=0; i<n; i++){
        printf("%d, %d\n", pPoints[i]->x, pPoints[i]->y);
        switch(i+1){
        case 1:
        case 10:
        case 100:
        case 1000:
        case 10000:
        case 100000:
        case 1000000:
        case 10000000:
        case 100000000:
            fprintf(stderr, "%9d: (%6d, %6d)\n", i+1, pPoints[i]->x, pPoints[i]->y);
        }
    }
    free(pPoints);
    free(points);
    return 0;
}

DouKaku?

格子点の列挙

Posted feedbacks - C

Index

Feed

Other

Link

Pathtraq