【题目地址】


【题目大意】
给出一个大蛋糕,现在切了若干刀，问{zd0}的一块的面积是多少。 其中蛋糕是圆形的，并且圆心在原点，而半径为10.0

【解题思路】
PS.这是一题我从来没有WA的题目(一直TLE)
我的做法是正确的，可是这题对时间的要求确实非常的高....暴力的做法已近比较难实现，本人实现了1小时多 (几乎300行)


【朴素算法(TLE)】
不难发现
(1) 切好的点集的凸壳 必然不存在某个边上有超过2个点
(2) 切好的点集的凸壳，其最小外接圆必然为原始的圆(显然)
(3) 对于凸壳内的许多多边形(凸的),不难发现无非是"外围"的若干凸多边形的面积可能需要加上该凸多边形的某条边所对应的圆弧(不知道怎么叫..)的面积

那么啥时候才需要把这些圆弧计算在内呢？显然是这个圆弧不是被某个切割线切出来的,因为被某个切割线切割以后，圆弧必然独立出来，于是这里需要用到点的hash,表示2个点是否属于一个切割线

于是搞好凸包以后，不断的进行多边形的切割，{zh1}对于所有的切割出来的凸多边形，分别考虑是否需要加上圆弧，{zh1}求{zd0}

该算法提交约10次，均告TLE

【优化】

(1) 注意到首先可以得到所有的圆弧的面积，而最终的答案 必然大于等于{zd0}的圆弧的面积
(2) 不难发现对于凸壳"内部" (所谓的内部，就是这个凸多边形的所有点都不在圆的边上), 继续切割它能得到解的必要的条件为 该 凸多边形的面积 大于 (注意是大于) {zd0}圆弧面积
于是可以在切割多边形的过程中添加入这个局部优化的剪枝(这样可以剪掉许多面积过小的凸多边形)

加了以上的优化，终于卡过了(PS.这题非常卡时间...)

赞，表示纪念{dy}次过50- 人AC 的题...

不过其实不难就对了

【程序代码】
no