这两天写了圆交和圆并
圆交和圆并都有非常优美的O(n^2logn)算法,AekdyCoin有讲
但是像这种求面积的题还可以用Simpson积分法
简单的说就是将一段函数积分用二次函数积分拟合
一听这种搞法就知道是乱搞……但是很多时候比较有用……
嗯……像是求圆并的话,可以这样做
将x轴某一点上各个圆并所对应的长度视为函数值,用Simpson积分拟合
圆并在x轴上某一点对应的长度比较好算
如图,蓝色的那一段就是这一点对应的函数值,那么实际上就是每个圆和直线求一次交,得到的一段线段再做一次线段覆盖
看的出来复杂度是比较高的……每求一次函数值就是O(n)
具体的拟合怎么做呢
对于一段区间(l,r)我们首先计算f(l),f(r),f(mid)
然后(l,r)对应的拟合积分就是(f(l)+f(r)+4*f(mid))*(r-l)/6
然后再分别计算(l,mid),(mid,r)的积分
如果误差<eps,认为这一段拟合正确,否则递归计算两个区间
又好想又好写~~
问题是,这样做真是乱搞的……
在做得时候要注意几个问题
一是最好确保积的这一段函数是连续的,否则极有可能出现4个峰分别在mid两边,你积出来得0的情况……
二是注意精度……如果输出要求精确到几位,你的eps最好比他高几个数量级……否则容易出错……而精度设高的代价为非常慢……
综上所述,Simpson积分法虽然不失为一个非常优秀的算法
但是由于他的种种问题,在可以想出正解或者有比他更好的算法的时候尽量少用……
优点就是适用范围广,好想好实现
如果没想出什么更好的算法就尽管用吧,总比没分好……
但是如果是ACM或者TC,CF之类的需要全部AC的慎用……或者eps精度高一点……
话说这样的考试一般不会出积分才能过的题吧……
SPOJ CIRU的代码 //此题为裸圆并
P.S:
bzoj上有道和这个一模一样的圆并,但是eps得设到1e-13才能AC,可见Simpson积分十分不稳定啊
分享到:
相关推荐
数值计算方法中关于复化Simpson积分和复化梯形积分的c语言程序源代码,并提供相应误差估算
几种数值积分方法new-cotes(梯形,simpson)gauss(legendre)复化求积(梯形 simpson)
这里是利用Simpson公式求积分与自适应复化Simpson公式求积分
计算方法教程 凌永祥 第四章第三题复化simpson公式求积分
自适应Simpson积分算法(MATLAB及C++实现代码)[文].pdf
1. 常用的数值积分方法(特别是梯形法、Simpson方法、 Cotes公式、Romberg算法以及Gauss 求积公式)的原理;2. 复合梯形公式,复合Simpson公式,Romberg算法的程序
【老生谈算法】自适应Simpson积分算法(MATLAB及C++实现代码).docx
MATLAB程序包括:复化梯形积分、复化Simpson、复化cotes、龙贝格积分程序源代码
包含了简单Simpson积分,复合Simpson,变步长Simpson积分
复化simpson公式计算定积分,matlab程序实现,需要输入积分函数、上下限和所分步数,希望能对大家的学习有帮助。
simpson积分法求函数的积分,有利于积分算法得到所需要的值
simpson积分器 时域积分对比频域积分
matlab中利用复化梯形公式和复化simpson公式实现积分运算,对于数值计算类课程很有帮助。
Simpson二重积分数值算法,注释比较详细
数值积分课程需编制自适应的Simpson公式,此代码采用递归函数,函数中采用了fcnchk函数,matlab6.5及以下版本会报错,只需将函数定义语句改成inline函数即可
用梯形公式和simpson公式求积分
基于MATLAB的复合Simpson数值积分法的研究与实验.pdf
变步长simpson积分c语言程序,期中f函数就是是被积函数。如果要改被积函数请改f函数
复化Simpson求积公式计算数值积分一·复化Simpson求积公式的数学理论 如果用分段二次插值函数近似被积函数,即在小区间上用Simpson公式计算积分近似值,就可导出复化Simpson公式。二·复化Simpson求积公式的算法和...
vc下用复化梯形积分法和复化Simpson积分法以及Gauss-Legendre求积法求解Fredholm积分方程,并配有MATLAB的测试程序