POJ 2588 집 판 연통

/**
            5   ，        AC   
          ：        ，        

      ：  1000*1000      ，                ，     
    n  ，         (x,y)   r      ，            （    < r），
        ，            。

      ：      ，    ，              ，    ，  
    1、                  ，        
    2、                   ，          ，      
    3、        ？    。
    4、        ？        。
    5、               0 n+1，                。
    6、                。            
     ：     2
                 400 400 500
                 600 600 500
                1、2,            
        <0,1> <1,2> <2,3>     0,1,2,3     3  
           0 3    ，         

            
*/
#include <math.h>
#include <stdio.h>
#include <string.h>
#define sqr(x) ((x)*(x))
#include <algorithm>

using namespace std;

const int M = 1005;

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

struct lr {
    double u, d;
    int i;
}l[M], r[M];    //               ，      

bool map[M][M]; // map[1][2] == true, 1、2     <1,2>
int path[M];    //          kruskal        

///////////////////////////////////////////
//       ，             ，
//                 ，   
//               ，     
//        AC
int find(int x) {
    if (x != path[x])
        path[x] = find(path[x]);
    return path[x];
}

//                 ，     
bool jud(lr tt[], double x, int n) {
    for (int i=0; i<n; i++)
        if (tt[i].u > x && tt[i].d < x)
            return false;
    return true;
}

int main() {

    int n;

    while (scanf("%d", &n)!=EOF)
    {
		memset(map, 0, sizeof (map));

		int ll=0, rr=0;
		//                         
		for (int i=1; i<=n; i++) {
			scanf("%lf%lf%lf", &p[i].x, &p[i].y, &p[i].r);
			if (p[i].y+p[i].r > 1000)   //        
				map[0][i] = map[i][0] = true;
			if (p[i].y-p[i].r < 0)      //        
				map[n+1][i] = map[i][n+1] = true;
            //                      

            //                    ，     
			if (p[i].x-p[i].r < 0) {    //        
                // l[ll].u, l[ll].d,l[0].i = i,    ll  ，
                //    i,           (l[ll].d, l[ll].u)
				l[ll].u = p[i].y + sqrt(sqr(p[i].r)-sqr(p[i].x));
				l[ll].d = p[i].y - sqrt(sqr(p[i].r)-sqr(p[i].x));
				l[ll++].i = i;

			}
			if (p[i].x+p[i].r > 1000) {
				r[rr].u = p[i].y + sqrt(sqr(p[i].r)-sqr(1000-p[i].x));
				r[rr].d = p[i].y - sqrt(sqr(p[i].r)-sqr(1000-p[i].x));
				r[rr++].i = i;
			}
		}
		//            ，                   
		for (int i=1; i<n; i++)
			for (int j=i+1; j<=n; j++) {
				if (p[i].r+p[j].r > sqrt(sqr(p[i].x-p[j].x)+sqr(p[i].y-p[j].y))) {
					map[i][j] = map[j][i] = true;
				}
			}
        //                    ，        

        //             
		for (int i=0; i<=n+1; i++)
			path[i] = i;
        ///////////////////////////////////////////////
        //                      ，
        //        a,b          
        // if (find(a) == find(b))
        //       a，b      ， a b  
        ///////////////////////////////////////////////
		for (int i=0; i<=n; i++)
			for (int j=i+1; j<=n+1; j++) {
				if (map[i][j]) {
					int x = find(i);
					int y = find(j);
					if (x != y)
						path[y] = x;
				}
			}

		if (find(n+1) == find(0))   //               ，   
			printf("Bill will be bitten.
");
        /////////////////////////////////////////////////
        //            ，     
        //         7、8 ，            
        //          ，     ，       
        ////////////////////////////////////////////////
		else {
			double lflag = -1, rflag = -1;
			// lflag             , rflag             
			double lu=1000, ld=0, ru=1000, rd=0;
            // lu             ，ld           

            /////////////////////////////////////////////////////
            //            (ld, lu),     find(a)==find(0)
            //  a        ，        1000,      ，
			for (int i=0; i<ll; i++) {
				if (find(l[i].i)==find(0) && l[i].d < lu)
					lu = l[i].d;
				if (find(l[i].i)==find(n+1) && l[i].u > ld)
					ld = l[i].u;
			}
			/////////////////////////////////////////////////////////
			//       1000     ，                
			//   ：l[ll].u == 1200 l[ll].d == 800, 1000  (800,1200)  
			if (jud(l,1000,ll) && lu==1000)
				lflag = 1000;
            /////////////////////////////////////////////
            //                      
            //              ，        ，  lflag       
			for (int i=0; i<ll; i++) {
				if (l[i].u<=lu && l[i].u>=ld && jud(l,l[i].u,ll) && lflag < l[i].u) {
					lflag = l[i].u;
				}
				if (l[i].d<=lu && l[i].d>=ld && jud(l,l[i].d,ll) && lflag < l[i].d) {
					lflag = l[i].d;
				}
			}

            //            
			for (int i=0; i<rr; i++) {
				if (find(r[i].i)==find(0) && r[i].d < ru)
					ru = r[i].d;
				if (find(r[i].i)==find(n+1) && r[i].u > rd)
					rd = l[i].u;
			}
			if (jud(r,1000,rr) && ru==1000)
				rflag = 1000;
			for (int i=0; i<rr; i++) {
				if (r[i].u<=ru && r[i].u>=rd && jud(r,r[i].u,rr) && rflag < r[i].u) {
					rflag = r[i].u;
				}
				if (r[i].d<=ru && r[i].d>=rd && jud(r,r[i].d,rr) && rflag < r[i].d) {
					rflag = r[i].d;
				}
			}

			if (ll == 0)
				lflag = 1000;
			if (rr == 0)
				rflag = 1000;
			if (rflag<0 || lflag<0)
				printf("Bill will be bitten.
");
			else
				printf("Bill enters at (0.00, %.2lf) and leaves at (1000.00, %.2lf).
", lflag, rflag);
		}
    }
    return 0;
}