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()
{int n,i,j,key,answer,k,h;
       
while(1)
       {answer=0;
    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;
*/        
    if(key||cir[i].n)answer++;
    }
    cout<<answer<<endl;
       }
return 0;
}