#P4642. 泡泡

    ID: 2635 传统题 4000ms 512MiB 尝试: 126 已通过: 41 难度: 8 上传者: 标签>难度分类提高+/省选-计算几何扫描线数据结构FHQ Treap 分裂合并维护顺序统计量事件同坐标排序数值计算与优化根式符号精确比较平方距离比较CF2500

泡泡

泡泡

题目描述

平面上有 nn 个圆形泡泡。输入保证任意两个泡泡的内部互不相交,可以在边界处外切。TB 把每一对相切的泡泡称为一对自然的泡泡。求这样的无序泡泡对数。

输入格式

第一行一个正整数 nn。

接下来 nn 行,每行三个整数 x,y,rx,y,r,表示一个泡泡的圆心 (x,y)(x,y) 和半径 rr。

输出格式

输出一行一个整数,表示相切的泡泡对数。

4
0 0 5
8 6 5
-6 8 5
2 14 5
4

数据范围

1≤n≤5000001\le n\le500000,−109≤x,y≤109-10^9\le x,y\le10^9,1≤r≤1091\le r\le10^9。