#! ruby # yukicoder My Practice # author: Leonardone @ NEETSDKASU def gs() gets.chomp end def gi() gets.to_i end def gss() gets.chomp.split end def gis() gss.map(&:to_i) end def nmapf(n,f) n.times.map{ __send__ f } end def arr2d(h,w,v=0) h.times.map{[v] * w} end def ngs(n) nmapf n,:gs end def ngi(n) nmapf n,:gi end def ngss(n) nmapf n,:gss end def ngis(n) nmapf n,:gis end def for2p(hr,wr,&pr) hr.each{|i|wr.each{|j| yield(i,j)}} end def nsum(n) n * (n + 1) / 2 end TEST_RUN = false =begin 1) D範囲に完全内包 1.1: 軸に接しない 3 1 10 9 100 1.2: 軸に接する 3 0 10 8 100 1.3: 軸をまたぐ 3 -1 10 7 100 1.4: 原点を含む -3 -4 10 8 100 2) D範囲を完全内包 -10 -12 15 14 9 3) 一部だけD範囲と重なる 3.1: 三角範囲Dに入る 3.1.1: 軸に接しない 2 3 12 11 10 3.1.2: 片軸にだけ接する 0 3 12 11 10 3.1.3: 両軸に接する 0 0 12 11 10 3.2: 台形範囲Dに入る 3.2.1: 軸に接しない 4 2 15 6 13 3.2.2: 片軸に接する 4 0 15 6 13 3.2.3: 両軸に接する 0 0 15 6 13 3.3: 五角形範囲Dに入る 3.3.1: 軸に接しない 5 2 16 12 24 3.3.2: 片軸に接する 5 0 16 12 24 3.3.3: 両軸に接する 0 0 16 12 24 4) Dの範囲の完全外側 10 13 19 18 11 [1] テストケース -3 -12 8 -1 11 [2] テストケース -13 -8 10 8 12 [3] テストケース 4 7 10 11 11 [4] テストケース 5 3 11 20 30 =end def bruteforce(x1, y1, x2, y2, d) count = 0 (y1..y2).each do |y| (x1..x2).each do |x| count += 1 if x.abs + y.abs <= d end end count end def bunkatsu(z1_,z2_) z1, z2 = [z1_, z2_].minmax z1a, z2a = [z1.abs, z2.abs].minmax case when z2 < 0 [[z1a, z2a]] when z2 == 0 [[0, 0], [1, z1a]] when z1 > 0 [[z1a, z2a]] when z1 == 0 [[0, 0], [1, z2a]] when z1 < 0 && 0 < z2 [[0, 0], [1, z1a], [1, z2a]] else sleep 10 [] end end # 4) Dの範囲の完全外側 def perfectly_outside?((x1, x2), (y1, y2), d) d < x1 + y1 end # 点 def dot?((x1, x2), (y1, y2), d) x1 == x2 && y1 == y2 && x1 == y1 end def dot_count((x1, x2), (y1, y2), d) count = 0 <= d - (x1 + y1) ? 1 : 0 puts "dot [%d, %d] * [%d, %d], count: %d" % [x1, x2, y1, y2, count] if TEST_RUN count end # 直線 def line?((x1, x2), (y1, y2), d) x1 == x2 || y1 == y2 end def line_count((x1, x2), (y1, y2), d) count = 0 if d < x2 + y2 count = d - (x1 + y1) + 1 else count = (x2 + y2) - (x1 + y1) + 1 end puts "line [%d, %d] * [%d, %d], count: %d" % [x1, x2, y1, y2, count] if TEST_RUN count end # 三角形 def triangle?((x1, x2), (y1, y2), d) return 0 if d <= [x1 + y2, x2 + y1].min end def triangle_count((x1, x2), (y1, y2), d) count = nsum(d - (x1 + y1) + 1) puts "triangle [%d, %d] * [%d, %d], count: %d" % [x1, x2, y1, y2, count] if TEST_RUN count end # 台形 def trapezoid?((x1, x2), (y1, y2), d) d <= [x1 + y2, x2 + y1].max end def trapezoid_count((x1, x2), (y1, y2), d) short_end, long_end = [x1 + y2, x2 + y1].minmax short_len = short_end - (x1 + y1) + 1 long_len = [d, long_end].min - (x1 + y1) + 1 count = (short_len * (long_len - short_len)) + nsum(short_len) puts "trapezoid [%d, %d] * [%d, %d], count: %d" % [x1, x2, y1, y2, count] if TEST_RUN puts "end: [%d, %d], len: [%d, %d]" % [short_end, long_end, short_len, long_len] if TEST_RUN count end # 五角形 def pentagon?((x1, x2), (y1, y2), d) [x1 + y2, x2 + y1].max < D end def pentagon_count((x1, x2), (y1, y2), d) count = (x2 - x1 + 1) * (y2 - y1 + 1) - nsum((x2 + y2) - d) puts "pentagon [%d, %d] * [%d, %d], count: %d" % [x1, x2, y1, y2, count] if TEST_RUN count end ################################################ X1,Y1,X2,Y2,D = gis puts "X1=%d, Y1=%d, X2=%d, Y2=%d, D=%d" % [X1, Y1, X2, Y2, D] if TEST_RUN bf = bruteforce(X1, Y1, X2, Y2, D) if TEST_RUN puts "bruteforce %d" % [bf] if TEST_RUN # 1) D範囲に完全内包 if [X1.abs, X2.abs].max + [Y1.abs, Y2.abs].max <= D puts "perfectly inside of D range" if TEST_RUN count = (X2 - X1).abs.succ * (Y2 - Y1).abs.succ puts count exit end # 2) D範囲を完全内包 if [X1..X2, Y1..Y2].all?{|r| r.include?(-D) && r.include?(D)} puts "perfectly inside of Square" if TEST_RUN count = nsum(D) * 4 + 1 puts count exit end xs = bunkatsu(X1, X2) ys = bunkatsu(Y1, Y2) puts "xs = %s" % [xs.to_s] if TEST_RUN puts "ys = %s" % [ys.to_s] if TEST_RUN count = 0 for2p(ys,xs) {|yt,xt| args = [xt, yt, D] next if perfectly_outside?(*args) case when dot?(*args) count += dot_count(*args) when line?(*args) count += line_count(*args) when triangle?(*args) count += triangle_count(*args) when trapezoid?(*args) count += trapezoid_count(*args) when pentagon?(*args) count += pentagon_count(*args) end } puts count puts (bf == count ? "" : "in") + "corrct!" if TEST_RUN