Submission #13406078

---

Source Code Expand

# Studying https://atcoder.jp/contests/abc168/tasks/abc168_f
#      and https://mobile.twitter.com/chokudai/status/1262023105888698369

N,M = gets.split.map(&:to_i)
縦線 = N.times.map{ gets.split.map(&:to_i) }
横線 = M.times.map{ gets.split.map(&:to_i) }

経線 = 縦線.map{|_,_,c| c }.uniq.sort
緯線 = 横線.map{|d,| d }.uniq.sort

GW = 経線.size*2+3 # INF ゾーンと壁で囲います(+4)。
GH = 緯線.size*2+3
GI = lambda{|横,縦|
	i = 経線.bsearch_index{|_| 横<=_ }||経線.size # 線分の端点の座標に対応する
	j = 緯線.bsearch_index{|_| 縦<=_ }||緯線.size
	i1 = 経線[i] != 横 ? 1 : 0 # 線分間の座標に対応するための補正
	j1 = 緯線[j] != 縦 ? 1 : 0
	next (2+2*j-j1)*GW+(2+2*i-i1)
}
下 = lambda{|i|
	(i/GW+1)/2*2*GW + i%GW
}
上 = lambda{|i|
	i/GW/2*2*GW + i%GW
}
右 = lambda{|i|
	(i+1)/2*2
}
左 = lambda{|i|
	i/2*2
}
Grid = lambda{|g|
	縦線.each{|a,b,c|
		下[GI[c,a]].step(上[GI[c,b]], GW){|i|
			g[i] = '0'
		}
	}
	i = 0
	GH.times{
		g[i] = g[i+GW-1] = '0'
		i += GW
	}

	横線.each{|d,e,f|
		右[GI[e,d]].upto(左[GI[f,d]]){|i|
			g[i] = '0'
		}
	}
	0.upto(GW-1){|i|
		g[i] = g[-1-i] = '0'
	}

	return g
}['1'*(GW*GH)]
Area = lambda{|a|
	(GW+1).upto(GW+GW-2){|i|
		a[i] = a[-1-i] = Float::INFINITY
	}
	i = GW+1
	(GH-2).times{
		a[i] = a[i+GW-3] = Float::INFINITY
		i += GW
	}

	heights = 緯線.each_cons(2).map{|y,z| z-y }
	widths = 経線.each_cons(2).map{|y,z| z-y }
	j = (GW+1)*3
	heights.each{|h|
		i = 0
		widths.each{|w|
			a[j+i] = h*w
			i += 2
		}
		j += GW+GW
	}

	return a
}[[0]*(GW*GH)]

area = 0
cow = GI[0,0]
Grid[cow] = '0'
Q = [cow]
while at = Q.shift
	area += Area[at]
	[-1,1,GW,-GW].each{|mv|
		next if Grid[at+mv] == '0'
		Grid[at+mv] = '0'
		Q << at+mv
	}
end

puts(area.finite? ? area : 'INF')

Submission Info

Judge Result