1688.txt

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

 

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

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,C,D;
	if(!A_B(a,b,A,B))return 0;
	if(!A_B(a,c,C,D))return 0;
	

	while(A<=B-2*pi)A+=2*pi;

	while(B<=A-2*pi)B+=2*pi;

	A+=B;
	B=A-B*2;
	C+=D;
	D=C-D*2;
	
	return (B>D?B:D)>(A<C?A:C);
}
	
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(p[i].x==p[j].x&&p[i].y==p[j].y)
			{
				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=a+1;b<n;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;
	long *p;
	ring=0;
	for(i=0;i<n;i++)
		if(!sign[i])find(i,-1);
	if(ring/2-no<0)p=new long[10000000];
		cout<<ring/2-no/*+1*/<<endl;
	}
	return 0;
}