加载中...
题解 P1756 【[NOI2009]描边】

前言

不得不说它是一道难题啊。弄了我$1$天才把程序写出来,结果始终只有$97pts
$,网上有两种说法,据BYVOID大牛说是精度不够的问题,他貌似用了$11$天把最后$3$分得到了,但是网上有人用了辛普森/纯计算/高精度实数依次做了比对,最后认为是最后一个点的数据错了。实际怎样不得而知,暂且认为我用的辛普森公式是对面积的近似计算,存在一定误差。

正文:

解法:辛普森公式。

算法思路:

题目的本质是去求一些长方体与圆的交面积,而这些图形放到一块后是一个不规则的图形,自然想到利用辛普森公式来求面积:

求出所有的连续区间$[a,b]$,然后计算出其对应的纵向的连续区间$f(a)$,$f(b)$,$f((a+b) \div 2)$,通过控制精度来用辛普森公式得到相对准确的区间面积,最后加上所有区间的面积就是最后解。

控制精度的方法是二分比较左右子区间与当前区间的面积差。

时间复杂度:

不好估算,与精度有关,精度控制得越高解越精确,但越耗时。实现时当精度在$10^{-9}$时,前$8$个点秒过,第$9$个点$3s$左右,第$10$个点$10s$左右。当精度在$10^{-17}$时,第$10$个点跑了几分钟(但是始终无法把最后3分得到)。

测试情况:

得到了$97pts$

细节处理:

可以将所有点适当旋转,随机改变图形的位置,来多次测试提高精度。

需要自己推导求矩形4顶点的公式与求交点的公式。


  目录
劳动
快乐