Posted at

オフラインリアルタイムどう書く E18 の実装例

More than 1 year has passed since last update.

問題 : http://nabetani.sakura.ne.jp/hena/orde18twintri/

実装リンク集 : https://qiita.com/Nabetani/items/891d07f4d645ec00ce9a

三角形をすべて含む矩形の面積を S として、

O(S)ぐらい、O(√S)ぐらい、, O(1)ぐらい、の3つの戦略がある。

私は O(S)ぐらい と O(√S)ぐらいの2つを実装した。

まずは O(S)ぐらい の、遅い方から。


ruby

class Triangle

def initialize( s )
x,y,@dir,h=s.scan( /(\d+)\,(\d+)([RLTB])(\d+)/ ).to_a.flatten
@x,@y,@h = [x,y,h].map(&:to_i)
end
def ranges
[ [@x-@h, @x+@h], [@y-@h, @y+@h] ]
end
def include?(x,y)
dx = x - @x
dy = y - @y
case @dir
when "R"
0<=-dx && -dx<@h && dy.abs <= dx.abs
when "L"
0<=dx && dx<@h && dy.abs <= dx.abs
when "T"
0<=dy && dy<@h && dx.abs <= dy.abs
when "B"
0<=-dy && -dy<@h && dx.abs <= dy.abs
else
raise "unexpected"
end
end
end

def solve_impl( a, b )
axr, ayr = a.ranges
bxr, byr = b.ranges
count=0
([ayr[0],byr[0]].max..[ayr[1],byr[1]].min).each do |y|
([axr[0],bxr[0]].max..[axr[1],bxr[1]].min).each do |x|
count += 1 if a.include?(x,y) && b.include?(x,y)
end
end
count
end

def solve( src )
ts = src.split("/").map{ |s| Triangle.new( s ) }
solve_impl( *ts ).to_s
end

DATA.each do |line|
num, src, expected = line.split(/\s+/)
actual = solve( src )
okay = actual==expected
puts( [(okay ? "ok" : "**NG**"), src, actual, expected ].join(" ") )
end

__END__
0 7,0R6/3,1B5 15
1 1,6L4/4,9R9 4
2 0,2R4/1,3B4 3
3 1,2L4/1,2L5 16
46 5621,8460T7612/2715,5697L8851 861192


三角形に含まれていそうなマス目を全部舐める作戦。

手元のマシンで1分弱。

ranges の返す値を工夫すると倍ぐらい速くなりそうだけど、気にしない気にしない。

続いて O(√S) ぐらいの実装。手元のマシンで1秒弱。


ruby

class Triangle

def initialize( src )
sx,sy,@dir,sh=src.scan( /(\d+)\,(\d+)([RLTB])(\d+)/ ).to_a.flatten
x,y,h = [sx,sy,sh].map(&:to_i)
@top=x+y*1i
@height = (h-1)*{"R"=>-1, "L"=>1, "T"=>1i, "B"=>-1i}[@dir]
end

def xrange
if @height.real==0
(@top.real-@height.imag.abs)..(@top.real+@height.imag.abs)
else
r = [@top.real, @top.real + @height.real]
r.min .. r.max
end
end

def y_at(x)
dx = x - @top.real
case @dir
when "R"
return [] unless (@height.real..0)===dx
[ @top.imag - dx.abs, @top.imag + dx.abs ]
when "L"
return [] unless (0..@height.real)===dx
[ @top.imag - dx.abs, @top.imag + dx.abs ]
when "B"
return [] unless dx.abs <= @height.imag.abs
[@top.imag - @height.imag.abs, @top.imag - dx.abs]
when "T"
return [] unless dx.abs <= @height.imag.abs
[@top.imag+dx.abs, @top.imag + @height.imag.abs ]
else
raise "unexpected"
end
end
end

def solve_impl(tris)
xrange = tris.map{ |t| t.xrange.minmax }.flatten.minmax
xrange.min.upto(xrange.max).sum{ |x|
y0, y1 = tris.map{ |t| t.y_at(x) }.sort
if y0.empty? || y1.empty?
0
else
r = [y1.first, 1+[y1.last, y0.last].min]
r==r.sort ? r[1]-r[0] : 0
end
}.to_s
end

def solve( src )
tris = src.split("/").map{ |t| Triangle.new(t) }
solve_impl( tris ).to_s
end

DATA.map{ |line|
num, src, expected = line.split(/\s+/)
actual = solve( src )
okay = expected==actual
puts( [(okay ? "ok" : "**NG**"), src, actual, expected ].join(" / ") )
okay
}.all?.tap{ |ok|
puts( ok ? "everything is okay" : "**SOMETHING WRONG***" )
}
__END__
0 7,0R6/3,1B5 15
1 1,6L4/4,9R9 4
2 0,2R4/1,3B4 3
3 1,2L4/1,2L5 16
46 5621,8460T7612/2715,5697L8851 861192


積分する感じ。

      r = [y1.first, 1+[y1.last, y0.last].min]

r==r.sort ? r[1]-r[0] : 0

の部分がなかなかぱっと書けないところだけど、これがちゃんと書ければ O(√S)ぐらいになる。

O(1) の実装は


  • 三角形の辺と辺の交点を求める

  • 求めた交点と三角形の頂点を合わせて「イベント点」とする

  • イベント点を x 座標順にソートする

  • イベント点を通る y軸に平行な線で、図形を分割する

  • 各図形は台形または三角形になるので、その面積を計算して合計する

という戦略なんだけど、実装するのがめんどくさそうなので今のところ書いていない。