【题意】
给出n个圆（n<=20），求有多少个不被圆覆盖的封闭区域
【输入】
第一行t，表示有t组数据
每组数据第一行为n表示有多少个圆
接下来n行分别描述n个圆，每行为x，y，r
【输出】
对于每组数据，输出有几个不被圆覆盖的封闭区域
Sample Input
2 4 100 100 20 100 135 20 135 100 20 135 135 20 1 10 10 40
Sample Output
1 0
离散化
07年论文有讲（高逸涵《与圆有关的离散化方法》）
对于任意一行y=k，都可以求出来不被圆覆盖的区间
观察可以很轻易的发现，区域连通性的变化，其实都发生在圆与圆交点所在的那一行或者是圆的上下处
我们将这些行称之为事件点
对于每个事件点，我们求他上下稍微偏移一点的区间
因为不在通过事件点，连通性不会变化
所以如果从下往上扫描的话，对于一个事件点的下偏移那行，跟上个事件点上偏移的那行，连通性是完全相同的
当然区间数也相同
接下来就是从一个事件点的下偏移转移到上偏移
如果他们之间区间有交集，那么这两个区间属于同一个联通块
一旦事件点下偏移有一个联通块没有上偏移的区间继承，那么说明有一个封闭的区间
程序写的十分乱。
program poj1688;
const
esp:extended=1e-8;
type
line=record
l,r:extended;
end;
node=record
x:extended;
incr:boolean;
end;
var
n,i,j,k,w,t,tot,all,total,o,ans,xx,oo,count:longint;
x,y,r:array [0..21] of longint;
event:array [0..601] of extended;
xl:array [0..61] of node;
temp:node;
ind:array [0..10001] of line;
own:array [0..10001] of longint;
sum:array [0..1] of longint;
dl:array [0..1,0..10001] of longint;
yes:array [0..10001] of boolean;
root,next,point:array [0..10001] of longint;
procedure swap_int (var a,b:longint);
var
i:longint;
begin
i:=a;
a:=b;
b:=i;
end;
procedure swap_dou (var a,b:extended);
var
i:extended;
begin
i:=a;
a:=b;
b:=i;
end;
procedure solve (i,j:longint);
var
left,right,t,mid,leftr,rightr:extended;
begin
t:=y[j]+(y[i]-y[j])*r[j]/(r[i]+r[j]);
left:=y[j]-r[j];
if y[i]-r[i]>left then left:=y[i]-r[i];
right:=t;
repeat
mid:=(left+right)/2;
leftr:=sqrt(sqr(r[j])-sqr(mid-y[j]));
rightr:=sqrt(sqr(r[i])-sqr(mid-y[i]));
if (x[j]+leftr<x[i]-rightr) or (x[j]-leftr>x[i]+rightr) then
left:=mid
else
right:=mid;
until abs(left-right)<1e-8;
inc(tot);
event[tot]:=left;
left:=t;
right:=y[j]+r[j];
if y[i]+r[i]<right then right:=y[i]+r[i];
repeat
mid:=(left+right)/2;
leftr:=sqrt(sqr(r[j])-sqr(mid-y[j]));
rightr:=sqrt(sqr(r[i])-sqr(mid-y[i]));
if (x[j]+leftr<x[i]-rightr) or (x[j]-leftr>x[i]+rightr) then
right:=mid
else
left:=mid;
until abs(left-right)<1e-8;
inc(tot);
event[tot]:=left;
end;
procedure qsort (s,e:longint);
var
i,j:longint;
k:extended;
begin
if s>=e then exit;
i:=s;
j:=e;
k:=event[(s+e) div 2];
while i<=j do
begin
while (i<=j)and(event[i]<k) do inc(i);
while (i<=j)and(event[j]>k) do dec(j);
if i>j then break;
swap_dou(event[i],event[j]);
inc(i);
dec(j);
end;
qsort(s,j);
qsort(i,e);
end;
procedure connect (s,e:longint);
begin
inc(oo);
point[oo]:=e;
next[oo]:=root[s];;
root[s]:=oo;
end;
procedure dfs (now:longint);
var
i:longint;
begin
yes[now]:=true;
i:=root[now];
while i<>0 do
begin
if not yes[point[i]] then
begin
own[point[i]]:=own[now];
if point[i]>=dl[o,1] then inc(count);
dfs(point[i]);
end;
i:=next[i];
end;
end;
procedure merge (now:longint);
var
i,j,k:longint;
a,b,t:extended;
begin
o:=1-o;
t:=event[now]-esp;
total:=0;
for i:=1 to n do
if sqr(y[i]-t)<sqr(r[i]) then
begin
inc(total);
xl[total].x:=x[i]-sqrt(sqr(r[i])-sqr(y[i]-t));
xl[total].incr:=true;
inc(total);
xl[total].x:=x[i]+sqrt(sqr(r[i])-sqr(y[i]-t));
xl[total].incr:=false;
end;
for i:=1 to total-1 do
for j:=i+1 to total do
if xl[i].x>xl[j].x then
begin
temp:=xl[i];
xl[i]:=xl[j];
xl[j]:=temp;
end;
k:=0;
w:=1;
for i:=1 to total do
if xl[i].incr then
begin
if k=0 then
begin
ind[dl[1-o,w]].r:=xl[i].x;
inc(w);
end;
inc(k);
end
else
begin
dec(k);
if k=0 then ind[dl[1-o,w]].l:=xl[i].x;
end;
t:=event[now]+esp;
total:=0;
for i:=1 to n do
if sqr(y[i]-t)<sqr(r[i]) then
begin
inc(total);
xl[total].x:=x[i]-sqrt(sqr(r[i])-sqr(y[i]-t));
xl[total].incr:=true;
inc(total);
xl[total].x:=x[i]+sqrt(sqr(r[i])-sqr(y[i]-t));
xl[total].incr:=false;
end;
for i:=1 to total-1 do
for j:=i+1 to total do
if xl[i].x>xl[j].x then
begin
temp:=xl[i];
xl[i]:=xl[j];
xl[j]:=temp;
end;
sum[o]:=1;
inc(all);
dl[o,1]:=all;
ind[all].l:=-1000000;
k:=0;
for i:=1 to total do
if xl[i].incr then
begin
if k=0 then ind[all].r:=xl[i].x;
inc(k);
end
else
begin
dec(k);
if k=0 then
begin
inc(all);
inc(sum[o]);
dl[o,sum[o]]:=all;
ind[all].l:=xl[i].x;
end;
end;
ind[all].r:=1000000;
for i:=1 to sum[o] do
yes[dl[o,i]]:=false;
for i:=1 to sum[1-o] do
yes[dl[1-o,i]]:=false;
for i:=1 to sum[1-o] do
root[dl[1-o,i]]:=0;
oo:=0;
for i:=1 to sum[1-o] do
for j:=1 to sum[1-o] do
if (i<>j)and(own[dl[1-o,i]]=own[dl[1-o,j]]) then
begin
connect(dl[1-o,i],dl[1-o,j]);
connect(dl[1-o,j],dl[1-o,i]);
end;
for i:=1 to sum[1-o] do
for j:=1 to sum[o] do
if not ((ind[dl[1-o,i]].l>ind[dl[o,j]].r)or(ind[dl[1-o,i]].r<ind[dl[o,j]].l)) then
begin
connect(dl[1-o,i],dl[o,j]);
connect(dl[o,j],dl[1-o,i]);
end;
for i:=1 to sum[1-o] do
if not yes[dl[1-o,i]] then
begin
count:=0;
dfs(dl[1-o,i]);
if count=0 then inc(ans);
end;
for i:=1 to sum[o] do
if not yes[dl[o,i]] then
begin
inc(xx);
own[dl[o,i]]:=xx;
end;
end;
begin
read(t);
while t<>0 do
begin
fillchar(root,sizeof(root),false);
fillchar(next,sizeof(next),0);
read(n);
for i:=1 to n do
read(x[i],y[i],r[i]);
for i:=1 to n-1 do
for j:=i+1 to n do
if x[i]-r[i]>x[j]-r[j] then
begin
swap_int(x[i],x[j]);
swap_int(y[i],y[j]);
swap_int(r[i],r[j]);
end;
tot:=0;
for i:=1 to n do
begin
inc(tot);
event[tot]:=y[i]-r[i];
inc(tot);
event[tot]:=y[i]+r[i];
end;
for i:=1 to n-1 do
for j:=i+1 to n do
if sqr(x[i]-x[j])+sqr(y[i]-y[j])<sqr(r[i]+r[j]) then
solve(i,j);
qsort(1,tot);
event[0]:=-10000000000;
o:=0;
sum[o]:=1;
all:=1;
ans:=0;
xx:=1;
dl[o,1]:=1;
own[1]:=1;
ind[1].l:=-1000000;
ind[1].r:=1000000;
for i:=1 to tot do
if event[i]-event[i-1]>esp then
merge(i);
writeln(ans);
dec(t);
end;
end.