1418.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"math.h"
#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;
}