[Shoi2013]扇形面积并

内存限制：256 MiB 时间限制：10 Sec

给定N个同心的扇形，求有多少面积，被至少K个扇形所覆盖。

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

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

输出一个整数ans，至少被K个扇形所覆盖的总面积等于π/2m×ans

保证答案不超过2^63-1


			【输入样例1】

3 8 2

1 -8 8

3 -7 3

5 -5 5

【输入样例2】

2 4 1

4 4 2

1 -4 4


			【输出样例1】

76

【输出样例2】

98

对于100%的数据，1≤n≤10^5, 1≤m≤10^6,1≤k≤5000,1≤ri≤10^5,-m≤a1,a2≤m

BZPRO Powered by Remmina.
Github Repository

#4418. [Shoi2013]扇形面积并