DouKaku? 3287 gemma: r≦√(n/2), 0°≦Θ≦45°の格...(格子点の列挙)

Comment detail

r≦√(n/2), 0°≦Θ≦45°の格子点を計算して、それを平面に8回、正方形のピザのように貼りつけると、見積もるべき格子点のリストができる。
それを原点からの距離で安定ソートする。
安定ソートで8回貼りつけたときの順番が保たれるので、仰角での順序付けを前もってやったことになる。
1000番めは同じく (-8 . 16)

(use srfi-1)

(define (test n)
  (take (stable-sort (append-map (lambda (x)
                                   (append-map (lambda (y)
                                                 (cond 
                                                  ((and (zero? x) (zero? y))
                                                   (list (cons x y)))
                                                  ((zero? x)
                                                   (list (cons x y)
                                                         (cons y x)
                                                         (cons (- y) x)
                                                         (cons x (- y))))
                                                  ((zero? y)
                                                   (list (cons x y)
                                                         (cons y x)
                                                         (cons (- x) y)
                                                         (cons y (- x))))
                                                  ((eq? x y)
                                                   (list (cons x y)
                                                         (cons (- y) x)
                                                         (cons (- x) (- y))
                                                         (cons y (- x))))
                                                  (else 
                                                   (list (cons x y)
                                                         (cons y x)
                                                         (cons (- y) x)
                                                         (cons (- x) y)
                                                         (cons (- x) (- y))
                                                         (cons (- y) (- x))
                                                         (cons y (- x))
                                                         (cons x (- y))))))
                                               (iota (+ x 1))))
                                 (iota (+ 1 (inexact->exact (ceiling (* (sqrt 2) (quotient (inexact->exact (ceiling (sqrt n))) 2)))))))
                     (lambda (p0 p1)
                       (< (+ (expt (car p0) 2) (expt (cdr p0) 2))
                          (+ (expt (car p1) 2) (expt (cdr p1) 2))))) n))

(for-each print (test 1000))

#3273 でも出てますが、これだと (4 . 3) が (5 . 0) より先になりません？

ご指摘のとおりです。
反時計回りに何枚目のピザカットかを保存するようにしました。
これならatan使ったほうがいいでしょう。
ピザカット戦略はろくなことがないと、うちの祖母も言ってました。

(use srfi-1)

(define (test n)
  (define R (+ 1 (inexact->exact (ceiling (* (sqrt 2) (quotient (inexact->exact (ceiling (sqrt n))) 2))))))
  (take (stable-sort (append-map (lambda (y)
                                   (append-map (lambda (x)
                                                 (cond 
                                                  ((and (zero? x) (zero? y))
                                                   (list (list x y 0)))
                                                  ((zero? x)
                                                   (list (list x y 0)
                                                         (list y x 2)
                                                         (list (- y) x 4)
                                                         (list x (- y) 6)))
                                                  ((zero? y)
                                                   (list (list x y 0)
                                                         (list y x 2)
                                                         (list (- x) y 4)
                                                         (list y (- x) 6)))
                                                  ((eq? x y)
                                                   (list (list x y 1)
                                                         (list (- y) x 3)
                                                         (list (- x) (- y) 5)
                                                         (list y (- x) 7)))
                                                  (else 
                                                   (list (list x y 0)
                                                         (list y x 1)
                                                         (list (- y) x 2)
                                                         (list (- x) y 3)
                                                         (list (- x) (- y) 4)
                                                         (list (- y) (- x) 5)
                                                         (list y (- x) 6)
                                                         (list x (- y) 7)))))
                                               (iota (- R y) y)))
                                 (iota R))
                     (lambda (p0 p1)
		       (let ((r0 (+ (expt (car p0) 2) (expt (cadr p0) 2)))
			     (r1 (+ (expt (car p1) 2) (expt (cadr p1) 2))))
			 (if (= r0 r1)
			     (< (caddr p0) (caddr p1))
			     (< r0 r1))))) n))

(for-each (lambda (x)
	    (print (take x 2)))
	  (test 1000))

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq