2016.txt

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

#include"iostream.h"
#include"math.h"
const double small=1e-7;

struct point
{
	double x,y,r;
}p[210];

int n,sign[210],edge[210][210],ring;

struct line
{double a,b,c;}
;
//ax+by=c;


double distance(point i,point j)
{
	return sqrt((i.x-j.x)*(i.x-j.x)+(i.y-j.y)*(i.y-j.y));
}


void find(int m,int none)
{int i;
sign[m]=1;
for(i=0;i<n;i++)
if(edge[m][i]&&i!=none){if(sign[i])ring++;else find(i,m);}	

}

double cheng(point a,point b,point c)
{
	return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

const double pi=3.14159265359;
typedef point cir;


bool A_B(cir a,cir b,double &A,double &B)
{
	double d;
	A=atan2(b.y-a.y,b.x-a.x);
	if((d=distance(a,b))==0)return 0;
	B=acos((a.r*a.r+d*d-b.r*b.r)/(2*a.r*d));

	return 1;
}
	

bool part_judge(cir a,cir b,cir c)
{
	double A,B;
	point p,q;
	
	if(!A_B(a,b,A,B))return 0;
		
	A+=B;
	B=A-B*2;
	p.x=a.x+a.r*cos(A);
	p.y=a.y+a.r*sin(A);
	q.x=a.x+a.r*cos(B);
	q.y=a.y+a.r*sin(B);
	
	return distance(p,c)>c.r&&distance(q,c)>c.r;
}
	
bool judge(cir a,cir b,cir c)
{
	return part_judge(a,b,c)&&part_judge(c,a,b)&&part_judge(b,c,a);
}

int main()
{int i,j,k,no,a,b,key;
	//int t;cin>>t;
	for(;/*t--*/;)
	{cin>>n;
	if(n==0)break;
	for(i=0;i<n;i++)
	{
		cin>>p[i].x>>p[i].y>>p[i].r;
		for(j=0;j<i;j++)
			if(distance(p[i],p[j])<=abs(p[i].r==p[j].r))
			{
				p[j].r=p[i].r>p[j].r?p[i].r:p[j].r;
				n--;i--;
				break;
			}
	}
	

	for(i=0;i<n;i++)
	for(j=0;j<n;j++)edge[i][j]=0;	
	
	for(i=0;i<n;i++)
	for(j=i+1;j<n;j++)
	{
		if(distance(p[i],p[j])<p[i].r+p[j].r)
		{key=1;
		for(a=0;a<i&&key;a++)
		for(b=0;b<a;b++)
		if(edge[a][b]&&cheng(p[i],p[a],p[b])*cheng(p[j],p[a],p[b])<0&&
			cheng(p[a],p[i],p[j])*cheng(p[b],p[i],p[j])<0)
		{key=0;break;}
	
		if(key)edge[i][j]=edge[j][i]=1;
//	cout<<i<<":"<<j<<endl;
		}
	}

	no=0;
	double h;
	for(i=0;i<n;i++)
	for(j=i+1;j<n;j++)
	for(k=j+1;k<n;k++)
	if(edge[i][j]&&edge[j][k]&&edge[k][i])
	{for(a=0;a<n;a++)
	 if(a!=i&&a!=j&&a!=k)
	 {h=cheng(p[a],p[i],p[j]);
	  if(h*cheng(p[a],p[j],p[k])<=0)continue;
      if(h*cheng(p[a],p[k],p[i])<=0)continue;
	  break;	 
	 }
	 if(a<n)continue;
	 if(!judge(p[i],p[j],p[k]))no++;
	}

	for(i=0;i<n;i++)sign[i]=0;
	
	ring=0;
	for(i=0;i<n;i++)
		if(!sign[i])find(i,-1);
	
		cout<<ring/2-no+1<<endl;
	}
	return 0;
}