格子点の列挙

30分プログラム、その156。格子点の列挙。

二次元平面上の格子点(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

使い方

$ ruby lattice.rb
<0,0>
<1,0>
<0,1>
<-1,0>
<0,-1>
<1,1>
<-1,1>
<1,-1>
<-1,-1>
<2,0>

ソースコード

反時計回りで、どちらが先にくるかはアークタンジェントで計算する。

#! /opt/local/bin/ruby -w
# -*- mode:ruby; coding:utf-8 -*-
#
# lattice.rb -
#
# Copyright(C) 2007 by mzp
# Author: MIZUNO Hiroki <hiroki1124@gmail.com> 
# http://mzp.sakura.ne.jp/
#
# Timestamp: 2007/10/06 18:05:40
#
# This program is free software; you can redistribute it and/or
# modify it under the same terms as Ruby itself.
#

# 配列でこれを実現すると、flattenで展開されてしまう
Point = Struct.new 'Point',:x,:y
class Point
  def to_s
    "<#{x},#{y}>"
  end
end

range = -20..20

points = range.map{|x|
  range.map{|y|
    Point.new x,y
  }
}.flatten

def dist(point)
  point.x*point.x + point.y*point.y
end

def atan(point)
  r = Math.atan2 point.y,point.x
  if r < 0 then
    Math::PI - r
  else
    r
  end
end

puts points.sort{|a,b|
  d = dist(a) <=> dist(b)

  if d == 0 then
    atan(a) <=> atan(b)
  else
    d
  end
}[0,1000]

参考

• 過去の30分プログラム
• http://ja.doukaku.org/65/