Submission #13413181

---

Source Code Expand

# Studying https://atcoder.jp/contests/abc168/tasks/abc168_f

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+1 # 大外で壁になる線分の外側に１マス確保する。牛さんがそこにいる可能性もある。
GH = 緯線.size+1
HI = lambda{|横,下げ=false| # 0 番目のマス目の右側に 0 番目の縦線が配置される関係から、基本的に線分の座標は右へ、下へ切り上げられる。
	i = 経線.bsearch_index{|_| 横<=_ }||経線.size
	i1 = 下げ && 経線[i] != 横 ? 1 : 0
	next i-i1
}
VI = lambda{|縦,下げ=false|
	j = 緯線.bsearch_index{|_| 縦<=_ }||緯線.size
	j1 = 下げ && 緯線[j] != 縦 ? 1 : 0
	next j-j1
}
GI = lambda{|横,縦,下げ=false|
	next VI[縦,下げ]*GW + HI[横,下げ]
}

面積 = lambda{|gi|
	b,r = gi.divmod(GW)
	next Float::INFINITY unless (1...経線.size).include?(r) && (1...緯線.size).include?(b)
	next (経線[r]-経線[r-1]) * (緯線[b]-緯線[b-1])
}

縦線 = 縦線.inject(Array.new(経線.size){ [] }){|_,(a,b,c)|
	_[HI[c]] << [VI[a],VI[b,true]]
	next _
}
横線 = 横線.inject(Array.new(緯線.size){ [] }){|_,(d,e,f)|
	_[VI[d]] << [HI[e],HI[f,true]]
	next _
}

右？ = lambda{|gi|
	b,r = gi.divmod(GW)
	next r+1 < GW && ! 縦線[r].any?{|s,e| b-1 < e && s < b }
}
左？ = lambda{|gi|
	b,r = gi.divmod(GW)
	next 0 < r && ! 縦線[r-1].any?{|s,e| b-1 < e && s < b }
}
下？ = lambda{|gi|
	b,r = gi.divmod(GW)
	next b+1 < GH && ! 横線[b].any?{|s,e| r-1 < e && s < r }
}
上？ = lambda{|gi|
	b,r = gi.divmod(GW)
	next 0 < b && ! 横線[b-1].any?{|s,e| r-1 < e && s < r }
}

area = 0
Cow = GI[0,0]
Qd = [false]*(GW*GH)
Qd[Cow] = true;
Q = [Cow]
while at = Q.shift
	area += 面積[at]
	(puts'INF'; exit) if area.infinite?

	(Q<<at+1;  Qd[at+1]  = true) if 右？[at] && ! Qd[at+1]
	(Q<<at-1;  Qd[at-1]  = true) if 左？[at] && ! Qd[at-1]
	(Q<<at+GW; Qd[at+GW] = true) if 下？[at] && ! Qd[at+GW]
	(Q<<at-GW; Qd[at-GW] = true) if 上？[at] && ! Qd[at-GW]
end

p area

Submission Info

Judge Result