#4418. [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