AOJ 2215 Three Silhouettes 未解《挑战程序设计竞赛》-码农场

挑战程序设计竞赛

三面剪影：给定x，y，z三个面上的投影，求确定的3个多角柱相交部分的体积。

输入格式：

n_x表示垂直于x轴的平面上的点个数，紧接着是它们的逆时针序的坐标。以此类推，最后3个0表示输入终止。

输出格式：

输出每个测试用例对应的体积并换行。误差不超过10-3即可。

3.6与平面和空间打交道的计算几何

被这题难哭了，约莫一个月前看了题干，又看了出题方的思路讲解，还是没做出来。

这题是2010东大程序竞赛的赛题，当年0人AC，0人提交……

Problem L 三つのシルエット.png

连本书作者秋葉拓哉自己都没搞定，放到第三章练习题里面，令我感到来自作者的深深恶意。

Standings (UTPC2010).png

现在AOJ的statistic里面也只有2个人搞定了，这题似乎相当变态啊，亏了岩天桑和北川桑说180行代码就搞定了。

已知的参考资料有：

出题方给出的pdf：silhouette.pdf

大意是先分割为三角形，化成凸包。然后平面上三角形各边的投影面被其他平面上的三角形的边的投影面切断，得到2d的凸多角形……没有更详细的信息了。

暂时把资料整理在这里，解答只能等以后了。