C1334 [SHOI2013]扇形面积并

内存限制:256 MB 时间限制:1000 ms

题目描述

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

输入格式

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

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

输出

输出一个整数 $ans$,至少被 $K$ 个扇形所覆盖的总面积等于$\dfrac{π}{2m}×ans$。

保证答案不超过 $2^{63}-1$。

样例

样例输入 1

3 8 2 1 -8 8 3 -7 3 5 -5 5

样例输出 1

76

样例输入 2

2 4 1 4 4 2 1 -4 4

样例输出 2

98

提示

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