2588.txt

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

Problem Id:2588  User Id:fzk 
Memory:64K  Time:45MS
Language:C++  Result:Accepted

Source 

#include"stdio.h"
#include"math.h"

const double eps=1e-7;

struct cir
{
	double x,y,r;
}c[1000];

inline bool edge(cir &a,cir &b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))<=a.r+b.r;
}

int n;

bool init()
{
	int i;
	
	if(scanf("%d",&n)!=1)return false;

	for(i=0;i<n;i++)
		scanf("%lf %lf %lf",&c[i].x,&c[i].y,&c[i].r);

	return true;
}
inline bool touch_up(cir &a)
{
	return a.y+a.r>=1000;
}

inline bool touch_down(cir &a)
{
	return a.y-a.r<=0;
}
inline bool touch_left(cir &a)
{
	return a.x-a.r<=0;
}
inline bool touch_right(cir &a)
{
	return a.x+a.r>=1000;
}
double f(cir &a,double x)
{
	return a.y-sqrt(a.r*a.r-(a.x-x)*(a.x-x));
}
bool sign[1000];
double l,r;
bool search(int s)
{
	double temp;
	sign[s] = true;
	if(touch_down(c[s]))
		return false;
	if(touch_left(c[s]))
	{
		temp=f(c[s],0);
		if(temp<l)l=temp;
	}
	if(touch_right(c[s]))
	{
		temp=f(c[s],1000);
		if(temp<r)r=temp;
	}
	for(int i=0;i<n;i++)
	{
		if(!sign[i]&&edge(c[s],c[i]))
			if(!search(i))return false;
	}
	return true;
}
void doit()
{
	int i;
	for(i=0;i<n;i++)
		sign[i] = false;
	
	l=1000,r=1000;
	
	for(i=0;i<n;i++)
	if(!sign[i]&&touch_up(c[i]))
	{
		if(!search(i))
		{
			printf("Bill will be bitten.\n");
			return ;
		}
	}
	
	printf("Bill enters at (0.00, %.2lf) and leaves at (1000.00, %.2lf).\n",l,r);
}
int main()
{
	while(init())
	{
		doit();
	}
	return 0;
}