P3997 [SHOI2013]扇形面积并

    • 25通过
    • 77提交
  • 题目提供者 chen_zhe 管理员
  • 评测方式 云端评测
  • 标签 线段树 各省省选 2013 上海 O2优化 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

    输入输出格式

    输入格式:

    第一行是三个整数 n,m,k。n 代表同心扇形个数,m代表将(−π ,π ]的角度

    区间平均分成2m 份。

    从第二行开始的 n 行,每行三个整数r,a1,a2。描述了一个圆心在原点的

    扇形,半径为r,圆心角是从弧度

    $π*a1/m$ 到 $π*a2/m$ (a1 不一定小于 a2)。

    输出格式:

    输出一个整数 ans , $π/2m*ans$ 等于至少k 个扇形所覆盖的总面积。

    数据保证答案在 $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

    说明

    1≤n≤10^5, 1≤m≤10^6,1≤k≤5000,1≤ri≤10^5,-m≤a1,a2≤m

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。