Posts Tagged “hyperspace”

Oct 10 2010

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

Posted by watashi in summary, tags: , ,

被问到上次ZOJ Monthly中的H题Special Special Judge III怎么用容斥原理做。确实我只在解题报告中提了一句可以这么做，然后就丢下了一段python代码跑了。现在来详细解释一下如何运用容斥原理求一个Hyperrectangle被Hyperplane切割后剩余部分的体积。这里假定n维空间内的Hyperrectangle为

\{(x_1,x_2,\cdots,x_n)|0\le x_1\le X_1, 0\le x_2\le X_2, \cdots, 0\le x_n\le X_n\}

而对应的Hyperplane为
a_1x_1+a_2x_2+\cdots+a_nx_n=b

那么我们实际要求的就是Convex
\{\mathbf{x}|0\le x_i\le X_i,\mathbf{a}^T\mathbf{x}\le b\}

的体积。

不妨先考虑两个二维平面上的例子：

mp-case-1

\{(x,y)|0\le x\le 4,0\le y\le 3,x+y\le 5\}

Comments 14 Comments »