cojs 西瓜 解题报告

首先我们要知道pick公式

设二维平面内任意多边形面积为S

设多边形内部整点数为a

设多边形边界的整点数为b

则满足S=a+b/2-1

变形得a=S-b/2+1

由期望的线性性质我们把问题转化为

1、求凸包面积的期望

2、求凸包边界整点数的期望

首先我们考虑如何算面积,对于任意凸多边形,我们可以以原点为划分点

对于每条边算叉积,叉积的和就是面积,很容易发现每条边的贡献是可以拆分的

显然我们可以枚举每条可能的边,对于这条边算他存在凸包的概率并乘以相应的贡献就可以辣

一共有n^2条边,所以这部分时间复杂度为O(n^2)

之后我们考虑如何算边界整点数的期望,更容易发现每条的边的贡献是可以拆分的

跟上面一个做法就可以了

至于每条边存在凸包的概率嘛,我就不再细说了

很容易推倒的公式,用心推一推就出来了

假设你已经知道概率的公式了

Em 好啦,我们现在来说一说O(n)的做法

很容易发现随着我们枚举的边的两个端点中间的点数的扩大,概率会越来越小

当概率不会对答案产生精度误差时,我们就可以不用计算辣

这就是O(n)的算法了

最后的最后一定要注意不能选退化的凸包,所以算概率的时候要考虑进去

PS:由于本人太辣鸡,并不能做出很大的严格凸包,所以这个题目只是简单的idea题喽

上一篇:C#[抽象类,接口]


下一篇:封装JDBC:实现简单ORM框架lfdb