C1494 [JLOI2016]圆的异或并

内存限制:256 MB 时间限制:3000 ms

题目描述

在平面直角坐标系中给定 $N$ 个圆。已知这些圆两两没有交点,即两圆的关系只存在相离和包含。求这些圆的异或面积并。异或面积并为:当一片区域在奇数个圆内则计算其面积,当一片区域在偶数个圆内则不考虑。

输入格式

第一行包含一个正整数 $N$,代表圆的个数。接下来 $N$ 行,每行 $3$ 个非负整数 $x,y,r$,表示一个圆心在 $(x,y)$,半径为 $r$ 的圆。保证 $|x|,|y|,≤10^8,r>0,N \le 200000$。

输出

仅一行一个整数,表示所有圆的异或面积并除以圆周率 $\pi$ 的结果。

样例

样例输入 1

2 0 0 1 0 0 2

样例输出 1

3

提示