Description：

给出平面上不相交不相切的 $n$ 个圆，求每个点的深度。

$1\le n \le 100000$

Solution：

把圆的上下端点纵坐标离散化，左右端点拆成 $\pm1$ 两个点并按横坐标排序。扫描线从左到右扫描，由题目的性质，任何时刻扫描线上都是一个括号序列。括号所在的实际位置不断变化，但括号之间的相对顺序不变，因此可以用平衡树( $set$ )维护括号的次序，每个圆插入时通过查询恰好比它高的那个括号，如果没有，那么深度是 $1$ ，如果是一个圆的上边界，那么深度是它的深度加一，如果是下边界，那么和他深度相同。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<set>

#include<cctype>

#include<cstring>

using namespace std;

typedef long long ll;

int n;

#define MAXN 100010

struct circle

{

	ll x,y,r;

}c[MAXN];

struct scan

{

	ll x;

	int type,id;

}w[MAXN << 1];

int tot = 0;

bool cmp_scan_x(scan a,scan b){return (a.x == b.x ? a.type < b.type : a.x < b.x);}

struct bracket

{

	ll x,y,r;

	int type,id;

	double height(ll pos)const{return (double)y + sqrt((double)r * (double)r - (double)(x - pos) * (double)(x - pos)) * (double)type;}

	bool operator < (bracket b)const

	{

		if(x == b.x && y == b.y && r == b.r)return type < b.type;

		ll pos = max(x - r,b.x - b.r);

		return height(pos) < b.height(pos);

	}

}b[MAXN << 1];

int dep[MAXN];

int ans[MAXN];

void work()

{

	scanf("%d",&n);

	tot = 0;

	for(int i = 1;i <= n;++i)

	{

		scanf("%lld%lld%lld",&c[i].x,&c[i].y,&c[i].r);

		++tot;w[tot].x = c[i].x - c[i].r;w[tot].type =  1;w[tot].id = i;

		++tot;w[tot].x = c[i].x + c[i].r;w[tot].type = -1;w[tot].id = i;

	}

	sort(w + 1,w + 1 + 2 * n,cmp_scan_x);

	set<bracket> s;

	memset(dep,0,sizeof(dep));

	for(int i = 1;i <= 2 * n;++i)

	{

		int id = w[i].id;

		bracket b1 = (bracket){c[id].x,c[id].y,c[id].r,-1,id};

		bracket b2 = (bracket){c[id].x,c[id].y,c[id].r, 1,id};

		if(w[i].type == -1)

		{

			s.erase(b1);

			s.erase(b2);

		}

		else

		{

			s.insert(b1);

			s.insert(b2);

			set<bracket>::iterator it = s.find(b1);

			if(it == s.begin())dep[w[i].id] = 1;

			else

			{

				--it;

				if(it -> type == 1)dep[w[i].id] = dep[it -> id];

				else dep[w[i].id] = dep[it -> id] + 1;

			}

		}

	}

	memset(ans,0,sizeof(ans));

	for(int i = 1;i <= n;++i)ans[dep[i]]++;

	for(int i = 1;i <= n && ans[i] != 0;++i)printf("%d\n",ans[i]);

	return;

}

int main()

{

	int testcases;

	scanf("%d",&testcases);

	while(testcases--)work();

	return 0;

}