小红的相切直线
题号:NC317567
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}平面上给定 n 个圆,第 i 个圆的圆心为 (x_i, y_i),半径为 r_i。请你找出一条平行于坐标轴(即水平或竖直)的直线,使得这条直线与尽可能多的圆相切。你只需要输出这条直线能与多少圆相切即可。

输入描述:

\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leqq T\leqq 10^5\right) 代表数据组数,每组测试数据描述如下:

\hspace{15pt}第一行一个整数 n (1 \leqq n \leqq 2\times 10^5),表示圆的个数。

\hspace{15pt}接下来 n 行,每行三个整数 x_i, y_i, r_i (-10^9 \leqq x_i, y_i \leqq 10^9,\ 1 \leqq r_i \leqq 10^9),表示第 i 个圆的圆心坐标和半径。

\hspace{15pt}除此之外,保证单个测试文件的 n 之和不超过 2 \times 10^5

输出描述:

\hspace{15pt}对于每组测试数据,新起一行。

\hspace{15pt}输出一行一个整数,表示最多能与多少个圆相切。
示例1

输入

复制
1
3
0 0 1
2 0 1
2 2 1

输出

复制
3