# Poj Solution 1418

```http://poj.org/problem?id=1418

#include<iostream>
#include"math.h"
using namespace std;
#define MSIZE 1000
const double pi=3.14159265358979324;
const double eps=1e-15;
struct point
{double x,y;};

struct typearc
{double a,b;};

struct typecir
{point ct;
double r;
typearc arc[360];
int n;
};

int cmp(double a,double b)
{if(fabs(a-b)<eps)return 0;
if(a>b)return 1;
return -1;
}

inline double jl(point &a,point &b)
{return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}

inline int div(typearc &arc1,typearc &arc2)
{if(cmp(arc1.a,arc2.b)>=0||cmp(arc1.b,arc2.a)<=0)return 0;
if(cmp(arc1.a,arc2.a)>=0&&cmp(arc1.b,arc2.b)<=0)return -1;
if(cmp(arc1.a,arc2.a)<0&&cmp(arc1.b,arc2.b)>0)return 3;
if(cmp(arc1.a,arc2.a)>=0)return 1;
return 2;
}

int div_arc(typecir &c,typearc &arc)
{int i,j,result,key=0,num=c.n;typearc t;
for(i=0;i<num;i++)
{result=div(c.arc[i],arc);
//    cout<<"result"<<result<<endl;
//    cout<<arc.a<<' '<<arc.b<<' '<<c.arc[i].a<<' '<<c.arc[i].b<<endl;
if(result==0)continue;
key=1;
t=c.arc[i];
for(j=i;j<c.n-1;j++)c.arc[j]=c.arc[j+1];
i--;num--;
switch(result)
{case -1:c.n--;break;
case 3:c.arc[c.n-1].a=t.a;
c.arc[c.n-1].b=arc.a;
c.arc[c.n].a=arc.b;
c.arc[c.n].b=t.b;
c.n++;break;
case 1:c.arc[c.n-1].a=arc.b;
c.arc[c.n-1].b=t.b;
break;
case 2:c.arc[c.n-1].a=t.a;
c.arc[c.n-1].b=arc.a;
break;
}

}
return key;
}

typearc jiao(typecir &a,typecir &b)
{typearc arc;
double da,d,l_ab,l,p;
l_ab=jl(a.ct,b.ct);
da=asin((b.ct.y-a.ct.y)/l_ab);
if(cmp(a.ct.x,b.ct.x)>0)da=pi-da;
if(cmp(da,0)<0)da=2*pi+da;
//    cout<<da<<endl;

p=(a.r+b.r+l_ab)/2;
l=2*sqrt(p*(p-a.r)*(p-b.r)*(p-l_ab))/l_ab;
d=asin(l/a.r);

if(cmp(l_ab*l_ab+a.r*a.r,b.r*b.r)<0)d=pi-d;
arc.a=da-d;
arc.b=da+d;
return arc;
}

int c_c_type(typecir &a,typecir &b)
{double l=jl(a.ct,b.ct);
if(cmp(l,a.r+b.r)>=0)return 0;
if(cmp(l,fabs(a.r-b.r))<=0)return -1;
return 1;
}

int doit(typecir &c1,typecir &c2)
//judge cir2
{int i,key=0;typearc arc,arct;
switch(c_c_type(c1,c2))
{case 0:return 0;
case -1:if(cmp(c2.r,c1.r)<=0)c2.n=0;
if(cmp(c1.r,c2.r)<0)if(c1.n){c1.n=0;return 1;}
return 0;
case 1:arc=jiao(c1,c2);
if(cmp(arc.b,2*pi)>0){arc.b-=2*pi;arc.a-=2*pi;}
if(cmp(arc.a,0)<0){arct.a=arc.a+2*pi;arct.b=2*pi;arc.a=0;
key|=div_arc(c1,arc);
key|=div_arc(c1,arct);    }
else  key|=div_arc(c1,arc);
arc=jiao(c2,c1);
if(cmp(arc.b,2*pi)>0){arc.b-=2*pi;arc.a-=2*pi;}
if(cmp(arc.a,0)<0){arct.a=arc.a+2*pi;arct.b=2*pi;arc.a=0;
div_arc(c2,arc);
div_arc(c2,arct);  }
else  div_arc(c2,arc);
return key;
}
return 0;
}

typecir cir[100];

int main()

while(1)
cin>>n;if(n==0)break;
for(i=n-1;i>=0;i--)
{cin>>cir[i].ct.x>>cir[i].ct.y>>cir[i].r;
cir[i].ct.x*=MSIZE;cir[i].ct.y*=MSIZE;cir[i].r*=MSIZE;
cir[i].n=1;cir[i].arc[0].a=0;cir[i].arc[0].b=2*pi;
}

for(i=0;i<n;i++)
{key=0;

for(j=0;j<i;j++)
key+=doit(cir[j],cir[i]);
/*
for(k=0;k<=i;k++)
{cout<<k+1<<" :";
for(h=0;h<cir[k].n;h++)cout<<cir[k].arc[h].a/pi*180
<<'&'<<cir[k].arc[h].b/pi*180<<' ';
cout<<endl;
}
*/
//    cout<<key<<endl;
/*
k=0;
for(j=0;j<cir[i].n;j++)
if(cir[i].arc[j].b-cir[i].arc[j].a>=eps)break;
if(j<cir[i].n)k=1;
*/