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.

Leave a Reply

Your email address will not be published. Required fields are marked *