#P3146. [Feyat Cup1.5]Cir

    ID: 2310 传统题 1000ms 512MiB 尝试: 78 已通过: 13 难度: 10 上传者: 标签>难度分类省选/NOI-计算几何扫描线数据结构Treap动态规划树形 DP博弈论SG 函数异或合并异或 Trie字符串Trie 合并mex 计算标记复合CF2900

[Feyat Cup1.5]Cir

[Feyat Cup 1.5] Cir

题目描述

Saber 喜欢吃东西,常说王容易肚子饿。一篇讨论灵长类摄食行为的文章里,还流传着一个关于狗狗的力量和人类命运的故事。

传说地球曾拒绝阳光,用许多圆形阴霾笼罩大陆。万物即将凋零之际,人类与星球约定以一场游戏决定胜负。法法塔从记载中得知,双方几乎凭运气行动,最后人类获胜,让自然得以延续。她想知道,面对按最优策略行动的对手,先手第一步有哪些地点能保证获胜。

地面上有 nn 个圆形阴霾。两方轮流行动,每次选择一个仍被阴霾笼罩的点,驱散所有覆盖该点的阴霾。每个被驱散的圆形阴霾整体消失。驱散最后一片阴霾的一方获胜。求先手第一步选择后能保证获胜的所有点所占的面积。

输入格式

第一行有一个正整数 nn。

接下来 nn 行,每行有三个实数 xi,yi,rix_i,y_i,r_i,表示第 ii 个圆形阴霾的圆心 (xi,yi)(x_i,y_i) 和半径 rir_i。

正式数据中,第一个圆的圆心为 (0,0)(0,0),半径为 10610^6,其余各圆都包含在这个圆内。任意两个圆的边界不相交。样例的外圆半径取 1010。

输出格式

输出一行一个实数,表示先手第一步能保证获胜的地点的总面积,保留六位小数。

样例

3
0 0 10
0 0 5
0 0 1
3.141593

数据范围

1≤n≤1051\le n\le 10^5。