[Shoi2013]扇形面积并
时间限制:10s 空间限制:256MB
题目描述
给定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
题目来源
没有写明来源