# Poj Solution 2588

```http://poj.org/problem?id=2588

#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;
}
```
This entry was posted in poj. Bookmark the permalink.