[待解决] [+500威望+500财富+提升为荣誉会员] 凸多边形(polygon) [复制链接]

好那好难好难。

因为凸多边形交还是凸,所以求半平面交,然后把所得多边形的面积算出就行了.

半平面交 zzy 2006提出过一个很好的算法,看他的论文吧..

1、两个凸多边形相交后，相交的部分肯定也是一个凸多变形(平面几何中的定理？忘了，呵呵)。
2、既然也是凸多边形，只需找出相交部分的各个顶点。
3、交点坐标求法较复杂，a、首先判断是否相交，b、相交后求两相交顶点。

对于两个多边形A、B相交来说，新的交集多边形C顶点可以这样做：
如果一个多边形的顶点在另一个多边形内，则它是C的顶点；
如果两个多边形的边相交，则交点是C的顶点。
按照逆时针顺序扫描所有A、B的顶点，则得出的C的顶点也是逆时针的。因为只有相邻的两个顶点一个在内一个在外，才会产生一个交点，且这个交点的顺序不会逆于总生成序。
于是维护新的多边形顶点集，最后由向量乘法得到面积。
如果算法真的是这样的，那么NOIP出这样的题……十分不厚道

我觉得可以这样
用向量可推出由丝带拟定出的两直线的交点坐标公式
进而得到最终的线性规划约束方程
然后用海伦公式还是蒙特卡洛都可以了

更正:
我觉得可以这样
用向量可推出由四点确定出的两直线的交点坐标公式
进而得到最终的线性规划约束方程
然后用海伦公式还是蒙特卡洛都可以了

我觉得蒙特卡洛没什么不行

蒙特卡洛应该可以,26楼观点不错,海伦公式似乎也可以,可程序不好编.晕~~  

好难