第11届浙江大学校赛比赛点评beta » CF35C

CF35C
CF35C.rb


class Rect
	def initialize(x, y, z)
		@a1 = x + y - z
		@a2 = x + y + z
		@b1 = x - y - z
		@b2 = x - y + z
		@valid = z >= 0
	end

	[:a1, :a2, :b1, :b2].each do |i|
		class_eval <<-"end_eval"
			def #{i}
				@#{i}
			end

			attr_writer :#{i}
		end_eval
	end

	def valid?
		@valid &&= (@a1 <= @a2 && @b1 <= @b2)
	end

	def invalid!
		@valid = false
	end

	def cut!(x1, y1, x2, y2)
		@a1 = [@a1, x1 + y1].max
		@a2 = [@a2, x2 + y2].min
		@b1 = [@b1, x1 - y2].max
		@b2 = [@b2, x2 - y1].min
	end

	def **(o)
		!(@a2 <= o.a1 || o.a2 <= @a1) && !(@b2 <= o.b1 || o.b2 <= @b1)
	end

	def /(o)
		r = []
		if @a1 <= o.a1
			r << self.clone
			r[-1].a2 = o.a1
			@a1 = o.a1
		end
		if @a2 >= o.a2
			r << self.clone
			r[-1].a1 = o.a2
			@a2 = o.a2
		end
		if @b1 <= o.b1
			r << self.clone
			r[-1].b2 = o.b1
			@b1 = o.b1
		end
		if @b2 >= o.b2
			r << self.clone
			r[-1].b1 = o.b2
			@b2 = o.b2
		end
		r
	end
end

def gao(n, m, s, a)
	b = [Rect.new(0, 0, 10000)]
	a.each do |x, y|
		c = Rect.new(x, y, s)
		b.size.times do |j|
			next unless b[j] ** c
			b += b[j] / c
			b[j].invalid!
		end
		b.reject!{|_| !_.valid?}
	end
	b.map!{|_| _ / _}.flatten!
	b.each do |_|
		if _.a1 == _.a2
			s = _.a1
			_.cut!([1, s - m].max, [1, s - n].max, [n, s - 1].min, [m, s - 1].min)
			_.b1 += 1 unless s.odd? == _.b1.odd?	## !!
			_.b2 -= 1 unless s.odd? == _.b2.odd?
		else
			s = _.b1
			_.cut!([1, 1 + s].max, [1, 1 - s].max, [n, m + s].min, [m, n - s].min)
			_.a1 += 1 unless s.odd? == _.a1.odd?	## !!
			_.a2 -= 1 unless s.odd? == _.a2.odd?
		end
	end
	b.reject!{|_| !_.valid?}
end

I = open('input.txt')
O = open('output.txt', 'w')

n, m = I.gets.split.map(&:to_i)
k = I.gets.to_i
t = I.gets.split.map(&:to_i)
a = k.times.map{|i| [t[i + i], t[i + i + 1]]}

l = 0
r = n + m
while l < r do
	s = (l + r) / 2
	b = gao(n, m, s, a)
	unless b.empty? then
		l = s + 1
	else
		r = s
	end
end
r -= 1

if r == 0
	# RE8
	O.puts "1 1"
else
	q = []
	gao(n, m, r, a).each do |_|
		_.a1.upto(_.a2) do |i|
			_.b1.upto(_.b2) do |j|
			#	q << [(i + j) / 2, (i - j) / 2] if (i + j).even? && (i - j).even?
				if (i + j).even? && (i - j).even?
					O.puts "#{(i + j) / 2} #{(i - j) / 2}"
					exit
				end
			end
		end
	end
end
# q.sort!.uniq!
# O.puts "#{q[0][0]} #{q[0][1]}"

__END__
# 	When 	Who 	Problem 	Lang 	Verdict 	Time 	Memory
234678 	Dec 29, 2010 10:31:27 AM 	watashi 	C - Fire Again 	Ruby 	Accepted 	90 ms 	3060 KB 
Leave a Reply