#PQJ112x346. QOJ 112_346

    ID: 2556 传统题 3000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:JLOI 2016线段树数学

QOJ 112_346

2016 年全国青少年信息学奥林匹克竞赛吉林省队选拔 第二试 圆的异或并 圆的异或并 【问题描述】 在平面直角坐标系中给定 𝑛 个圆。已知这些圆两两没有交点,即两圆的关 系只存在相离和包含。求这些圆的异或面积并。 异或面积并为:当一片区域在奇数个圆内则计算其面积,当一片区域在偶数 个圆内则不考虑。 【输入格式】 输入文件circle.in 的第一行包含一个正整数 𝑛,代表圆的个数。 接下来 𝑛 行,每行 3 个非负整数 𝑥, 𝑦, 𝑟,表示一个圆心在 (𝑥, 𝑦),半径为 𝑟 的圆。保证 |𝑥|, |𝑦|, 𝑟≤108,𝑟> 0。 【输出格式】 输出文件circle.out 仅一行一个整数,表示所有圆的异或面积并除以圆周率 𝜋 的结果。 【样例输入】 2 0 0 1 0 0 2 【样例输出】 3 【子任务】 测试点编号 𝑁 1~3 ≤5000 4~6 ≤30000 7~10 ≤200000