扇形面积并

这道题比矩形面积并友好多了。

题意:给定n个同心扇形,放置在一个被半径2m等分的圆中(圆是假想的),求被扇形覆盖了k次以上的关于面积的代数式$\frac{\pi}{2m}\times ans=S$,其中S为面积,输出ans;

输入:第一行是三个整数n,m,k。n代表同心扇形的个数,m用来等分$[-π,π]$的弧度。

从第二行开始的n行,每行三个整数r,a1,a2。描述了一个圆心在原点的扇形,半径为r,圆心角是从弧度$πa1/m$到$πa2/m$,a1可能大于a2,逆时针扫过的区域为该扇形面积。

思路:对于每个扇形,将其抽象为前端边和后端边。前端边的权值为1,后端边的权值为-1,逆时针转一周,依次将边的权值加入权值线段树中,对于每两条边之间,求面积,最后,求面积和即可。时间复杂度O(nlogn)(比不离散化的mlogn优)

数据结构:

问题一:离散化。离散化是OI中极其重要而且常用的手段。本人手上常用的离散化方式为stl map离散化。这种方法对于每一类型的数据离散化只需3行。

这一段代码可以把a离散化,其中a[i].first为原数,a[i].second为离散化后的值。

问题而:线段树。其实本题可以用树状数组,但是我觉得线段树方便一些,于是用了线段树。离散化后,整个圆形被分为了若干个部分。按照弧度从小到大把半径对应的点加上权值。由于扇形是同心的,所以线段树中每个节点保存的值就是当前节点对应的区间中被覆盖最多的部分被覆盖的次数。这样在寻找超过k次覆盖的部分时,就可以进行二分查找。

举个例子:

设e(i,j,c)表示每一条边对应的弧度,半径和权值。如果对于三条边(1,3,1),(2,5,1),(3,3,-1);那么在加入了第一条边时,线段树的状态就是{0,0,1,0,0,0,...}, 加入第二条边后就是{0,0,1,0,1,0,...}, 接着是{0,0,0,0,1,0,...}。如果我们设find(a,k)表示寻找节点a中最右端被覆盖了至少一次的地方,那么find(a,k)={find(a.lson,k-a.rson.tot)(a.rson.tot$<$k),find(a,rson,k)(a.rson.tot$>$=k)} ,这就有点划分树的意思了。