[吐槽]
嗯一开始接触到这个东西其实是因为某道凸包的题目好像可以用这个奇妙的方法来算
但其实了解也不是很深,只是觉得这个东西十分有意思,
所以先稍微写一下自己的想法,了解更多之后慢慢完善
[正题]
首先这个公式是长这样的:
取一个二次函数上(嗯。。貌似是这样的)的一段区间,左端点为$(l, hl)$,右端点为$(r, hr)$,中间的那个点为$(\frac{r-l}{2}, hmid)$
那么,这段的积分可以表示为:
$\frac{(r-l)*(hl+4*hmid+hr)}{6}$
但是这样往往会有很大的误差(并不是所有的函数图像都长成二次函数的样子的啊)
所以这个时候就可以用二分的方法来提高精度
当一段区间极其细或者极其扁的时候就可以看成一个二次函数了,也就是这时这样算出来的误差十分的小
这个时候就可以直接用那个公式啦
代码的话大概长这样
//这部分是二分逼近,esp是一个极小的值,但是不能太小不然的话会很慢
double simpson(double l,double r,double hl,double hr)
{
double mid=(l+r)/;
double hmid=get_val(mid);
//这里调用一个别的什么函数来得到mid的值
if ((abs(r-l)<=esp)||(abs(hl+hr-*hmid)<=esp))
return (r-l)*(hr+hl+*hmid)/;
return simpson(l,mid,hl,hmid)+simpson(mid,r,hmid,hr);
}