用容斥原理计算被Hyperplane切割后的Hyperrectangle体积 » RNGt

RNGt
RNGt.rb


def gao(x, y)
	ret = 0
	n = x.length
	(0 .. 2**n - 1).each do |i|
		z = 0
		f = 1
		(0 .. n - 1).each do |j|
			if (i & (1 << j)) != 0
				z += x[j]
				f = -f
			end
		end
		if y > z
			ret += f * (y - z) ** n
		end
	end
	return ret
end

re = gets.to_i
re.times do
	n, a, b = gets.split.map{|s| s.to_i}
	x = gets.split.map{|s| s.to_i}
	y = x.inject{|l, r| l + r}
	a, b = a + y, b + y
	x.map!{|s| s *= 2}
	c = gao(x, b) - gao(x, a)

	p = 1.0 * c
	p /= x.inject{|l, r| l * r}
	p /= (1 .. n).inject{|l, r| l * r}
	printf "%.9f\n", p
end

# TLE
Leave a Reply