#! 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 RANDOM_TEST = 0 TEST_RUN = (RANDOM_TEST == 0) && 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 make_random_case() x1 = rand(-20..20) y1 = rand(-20..20) x2 = x1 + rand(1..40) y2 = y1 + rand(1..40) d = rand(0..50) [x1, y1, x2, y2, d] end def bunkatsu(z1_,z2_) z1, z2 = [z1_, z2_].minmax zmin, zmax = [z1.abs, z2.abs].minmax case when zmin == 0 [[0, 0], [1, zmax]] when z2 < 0 || 0 < z1 [[zmin, zmax]] when z1 < 0 && 0 < z2 [[0, 0], [1, zmin], [1, zmax]] else sleep 10 [] end end # 4) Dの範囲の完全外側 def perfectly_outside?((x1, x2), (y1, y2), d) d < x1 + y1 end # Dの範囲に完全内包 def perfectly_inside?((x1, x2), (y1, y2), d) x2 + y2 <= d end def perfectly_inside_count((x1, x2), (y1, y2), d) count = (x2 - x1 + 1) * (y2 - y1 + 1) puts "inside [%d, %d] * [%d, %d], count: %d" % [x1, x2, y1, y2, count] if TEST_RUN count 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) 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 def solve(x1, y1, x2, y2, d) # 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 return count 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 return count 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 perfectly_inside?(*args) count += perfectly_inside_count(*args) 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 } count end ################################################ if RANDOM_TEST > 0 puts "starting RANDOM TEST" RANDOM_TEST.times do testcase = make_random_case bf = bruteforce(*testcase) count = solve(*testcase) next if bf == count puts "incorrect" puts "testcase: " + testcase.to_s puts "bf=%d count=%d" % [bf, count] break end puts "finished RANDOM TEST" exit end args = gis puts "X1=%d, Y1=%d, X2=%d, Y2=%d, D=%d" % args if TEST_RUN bf = bruteforce(*args) if TEST_RUN puts "bruteforce %d" % [bf] if TEST_RUN count = solve(*args) puts count puts (bf == count ? "" : "in") + "corrct!" if TEST_RUN