#include<cstdio>
#include<algorithm>
#include<cmath>
#define acc 0.0000000000001

using namespace std;

struct needle{
    double x,y,h,r;
};

needle nd[20],dmp;
int n,w;
double wr,ans;

pair<needle,needle> pnt;

pair<needle,needle> get_intersect(int i,int j){
    pair<needle,needle> p;
    double x0=nd[i].x,x1=nd[j].x,y0=nd[i].y,y1=nd[j].y,r0=nd[i].r,r1=nd[j].r;

    double d = sqrt((x0-x1)*(x0-x1)+(y0-y1)*(y0-y1));
//    printf("(%f,%f,%f)",r0,r1,d);
    if(r0 >=d+r1 || r1>=d+r0){
        p.first.x=-1;
        p.first.y=-1;
        p.second.x=-1;
        p.second.y=-1;
        return p;
    }
    if(r0+r1<d ){
//            printf(" asdf");
        p.first.x=x0+(x1-x0)*r0/d;
        p.first.y=y0+(y1-y0)*r0/d;
        p.second.x=x1+(x0-x1)*r1/d;
        p.second.y=y1+(y0-y1)*r1/d;
        dmp.x=x0+(x1-x0)*(x0+(d-x0-x1)/2)/d;
        dmp.y=y0+(y1-y0)*(y0+(d-y0-y1)/2)/d;
    }
    else{
        double a,h;
        a=(r0*r0-r1*r1+d*d)/(2*d);
        h=sqrt(r0*r0-a*a);
        double x2=x0+a*(x1-x0)/d;
        double y2=y0+a*(y1-y0)/d;
        p.first.x=x2-h*(y1-y0)/d; p.second.x=x2+h*(y1-y0)/d;
        p.first.y=y2+h*(x1-x0)/d; p.second.y=y2-h*(x1-x0)/d;
    }
    return p;
}

pair<needle,needle> get_wallIntersect(int i,double wr,int L){
    pair<needle,needle> p;
    double x0=nd[i].x,y0=nd[i].y,r0=nd[i].r,x1,y1,x2,y2;
/// (x-x0)^2 + (y-y0)^2 = r0^2
///  y = sqrt(r0^2-(x-x0)^2)+y0
///  x = sqrt(r0^2-(y-y0)^2)+x0
/// 4 lines : x = wr, y = wr, x = 100-wr, y = 100-wr
//    printf("(%f,%f,%f)",r0,r1,d);
    p.first.x=-1;
    p.first.y=-1;
    p.second.x=-1;
    p.second.y=-1;
    if(L==1){
        x1=wr;
        x2=wr;
        if(r0*r0-(x1-x0)*(x1-x0) < acc)
            return p;
        y1=sqrt(r0*r0-(x1-x0)*(x1-x0))+y0;
        y2=-sqrt(r0*r0-(x1-x0)*(x1-x0))+y0;
    }
    else if(L==2){
        x1=100-wr;
        x2=100-wr;

        if(r0*r0-(x1-x0)*(x1-x0) < acc)
            return p;
        y1=sqrt(r0*r0-(x1-x0)*(x1-x0))+y0;
        y2=-sqrt(r0*r0-(x1-x0)*(x1-x0))+y0;
    }
    else if(L==3){
        y1=wr;
        y2=wr;
        if(r0*r0-(y1-y0)*(y1-y0) < acc)
            return p;
        x1=sqrt(r0*r0-(y1-y0)*(y1-y0))+x0;
        x2=-sqrt(r0*r0-(y1-y0)*(y1-y0))+x0;
    }
    else if(L==4){
        y1=100-wr;
        y2=100-wr;
        if(r0*r0-(y1-y0)*(y1-y0) < acc)
            return p;
        x1=sqrt(r0*r0-(y1-y0)*(y1-y0))+x0;
        x2=-sqrt(r0*r0-(y1-y0)*(y1-y0))+x0;
    }
    p.first.x=x1;
    p.first.y=y1;
    p.second.x=x2;
    p.second.y=y2;
    return p;
}

bool isinside(needle p){
    double x=p.x,y=p.y,acc2=acc;
    if(x+acc2<0+wr||x-acc2>100-wr||y+acc2<0+wr||y-acc2>100-wr){
//    printf("(%f %f %f %f)\n",x-wr,y-wr,x-100+wr,y-100+wr);
//        printf(" outside");
        return true;
    }
    double d;
    for(int i=0;i<n;i++){
        d = sqrt((x-nd[i].x)*(x-nd[i].x)+(y-nd[i].y)*(y-nd[i].y));
        if(d+acc<nd[i].r){
//            printf(" %f\n",nd[i].r-d);
            return true;
        }
    }
    return false;
}

int main()
{
    int chk=0;
    double tmp;
    while(true){
        scanf("%d%d",&n,&w);
        if(n==0)
            return 0;
        ans = 0.0;
        for(int i=0;i<n;i++){
            scanf("%lf%lf%lf",&nd[i].x,&nd[i].y,&nd[i].h);
            //printf("%f",nd[i].x);
        }
        double lft=0.0,rgt=300.0,cur;
        while(lft<=rgt){
            cur = (lft+rgt)/2;
//            cur = 37.24602;
//            printf("%.2f: \n",cur);
            for(int i=0;i<n;i++){
                if(cur <= nd[i].h)
                    nd[i].r = cur;
                else{
                    tmp=cur-nd[i].h;
                    nd[i].r=sqrt(cur*cur-tmp*tmp);
                }
//                printf("\t%f %f %f\n",nd[i].x,nd[i].y,nd[i].r);
            }
            if(cur <= w){
                wr = cur;
            }
            else{
                tmp = cur-(double)w;
                wr=sqrt(cur*cur-tmp*tmp);
            }
//            printf(" %f] \n",wr);
            chk=0;
            for(int i=0;i<n;i++){
                for(int j=i+1;j<n;j++){
                    pnt = get_intersect(i,j);
                    if( (!isinside(pnt.first)) || (!isinside(pnt.second)) ){
//                        printf(" %d %d ",i,j);
                        chk=1;
                        break;
                    }

                }
                for(int L=1;L<=4;L++){
                    pnt = get_wallIntersect(i,wr,L);
                    if( (!isinside(pnt.first)) || (!isinside(pnt.second)) ){
//                        printf(" %d %d ",i,j);
                        chk=1;
                        break;
                    }
                }
                if(chk)
                    break;
            }
//            if(chk==0)
//                printf("==%f\n",cur);
            if(!chk){
                dmp.x = 0.0+wr; dmp.y = 0.0+wr;
                chk = chk || (!isinside(dmp));
                dmp.x = 0.0+wr; dmp.y = 100.0-wr;
                chk = chk || (!isinside(dmp));
                dmp.x = 100.0-wr; dmp.y = 0.0+wr;
                chk = chk || (!isinside(dmp));
                dmp.x = 100.0-wr; dmp.y = 100.0-wr;
                chk = chk || (!isinside(dmp));
            }
            if(chk){
                ans = cur;
                lft = cur+acc;
            }
            else{
                rgt = cur-acc;
            }
        }
        printf("%.5f\n",ans);
    }
}


### Prompt

Please provide a CPP coded solution to the problem described below:

An open-top box having a square bottom is placed on the floor. You see a number of needles vertically planted on its bottom.

You want to place a largest possible spheric balloon touching the box bottom, interfering with none of the side walls nor the needles.

Java Specific: Submitted Java programs may not use "java.awt.geom.Area". You may use it for your debugging purposes.

Figure H.1 shows an example of a box with needles and the corresponding largest spheric balloon. It corresponds to the first dataset of the sample input below.

<image>
Figure H.1. The upper shows an example layout and the lower shows the largest spheric balloon that can be placed.



Input

The input is a sequence of datasets. Each dataset is formatted as follows.


n w
x1 y1 h1
:
xn yn hn


The first line of a dataset contains two positive integers, n and w, separated by a space. n represents the number of needles, and w represents the height of the side walls.

The bottom of the box is a 100 × 100 square. The corners of the bottom face are placed at positions (0, 0, 0), (0, 100, 0), (100, 100, 0), and (100, 0, 0).

Each of the n lines following the first line contains three integers, xi, yi, and hi. (xi, yi, 0) and hi represent the base position and the height of the i-th needle. No two needles stand at the same position.

You can assume that 1 ≤ n ≤ 10, 10 ≤ w ≤ 200, 0 < xi < 100, 0 < yi < 100 and 1 ≤ hi ≤ 200. You can ignore the thicknesses of the needles and the walls.

The end of the input is indicated by a line of two zeros. The number of datasets does not exceed 1000.

Output

For each dataset, output a single line containing the maximum radius of a balloon that can touch the bottom of the box without interfering with the side walls or the needles. The output should not contain an error greater than 0.0001.

Example

Input

5 16
70 66 40
38 52 20
40 35 10
70 30 10
20 60 10
1 100
54 75 200
1 10
90 10 1
1 11
54 75 200
3 10
53 60 1
61 38 1
45 48 1
4 10
20 20 10
20 80 10
80 20 10
80 80 10
0 0


Output

26.00000
39.00000
130.00000
49.49777
85.00000
95.00000

### Response

```cpp
#include<cstdio>
#include<algorithm>
#include<cmath>
#define acc 0.0000000000001

using namespace std;

struct needle{
    double x,y,h,r;
};

needle nd[20],dmp;
int n,w;
double wr,ans;

pair<needle,needle> pnt;

pair<needle,needle> get_intersect(int i,int j){
    pair<needle,needle> p;
    double x0=nd[i].x,x1=nd[j].x,y0=nd[i].y,y1=nd[j].y,r0=nd[i].r,r1=nd[j].r;

    double d = sqrt((x0-x1)*(x0-x1)+(y0-y1)*(y0-y1));
//    printf("(%f,%f,%f)",r0,r1,d);
    if(r0 >=d+r1 || r1>=d+r0){
        p.first.x=-1;
        p.first.y=-1;
        p.second.x=-1;
        p.second.y=-1;
        return p;
    }
    if(r0+r1<d ){
//            printf(" asdf");
        p.first.x=x0+(x1-x0)*r0/d;
        p.first.y=y0+(y1-y0)*r0/d;
        p.second.x=x1+(x0-x1)*r1/d;
        p.second.y=y1+(y0-y1)*r1/d;
        dmp.x=x0+(x1-x0)*(x0+(d-x0-x1)/2)/d;
        dmp.y=y0+(y1-y0)*(y0+(d-y0-y1)/2)/d;
    }
    else{
        double a,h;
        a=(r0*r0-r1*r1+d*d)/(2*d);
        h=sqrt(r0*r0-a*a);
        double x2=x0+a*(x1-x0)/d;
        double y2=y0+a*(y1-y0)/d;
        p.first.x=x2-h*(y1-y0)/d; p.second.x=x2+h*(y1-y0)/d;
        p.first.y=y2+h*(x1-x0)/d; p.second.y=y2-h*(x1-x0)/d;
    }
    return p;
}

pair<needle,needle> get_wallIntersect(int i,double wr,int L){
    pair<needle,needle> p;
    double x0=nd[i].x,y0=nd[i].y,r0=nd[i].r,x1,y1,x2,y2;
/// (x-x0)^2 + (y-y0)^2 = r0^2
///  y = sqrt(r0^2-(x-x0)^2)+y0
///  x = sqrt(r0^2-(y-y0)^2)+x0
/// 4 lines : x = wr, y = wr, x = 100-wr, y = 100-wr
//    printf("(%f,%f,%f)",r0,r1,d);
    p.first.x=-1;
    p.first.y=-1;
    p.second.x=-1;
    p.second.y=-1;
    if(L==1){
        x1=wr;
        x2=wr;
        if(r0*r0-(x1-x0)*(x1-x0) < acc)
            return p;
        y1=sqrt(r0*r0-(x1-x0)*(x1-x0))+y0;
        y2=-sqrt(r0*r0-(x1-x0)*(x1-x0))+y0;
    }
    else if(L==2){
        x1=100-wr;
        x2=100-wr;

        if(r0*r0-(x1-x0)*(x1-x0) < acc)
            return p;
        y1=sqrt(r0*r0-(x1-x0)*(x1-x0))+y0;
        y2=-sqrt(r0*r0-(x1-x0)*(x1-x0))+y0;
    }
    else if(L==3){
        y1=wr;
        y2=wr;
        if(r0*r0-(y1-y0)*(y1-y0) < acc)
            return p;
        x1=sqrt(r0*r0-(y1-y0)*(y1-y0))+x0;
        x2=-sqrt(r0*r0-(y1-y0)*(y1-y0))+x0;
    }
    else if(L==4){
        y1=100-wr;
        y2=100-wr;
        if(r0*r0-(y1-y0)*(y1-y0) < acc)
            return p;
        x1=sqrt(r0*r0-(y1-y0)*(y1-y0))+x0;
        x2=-sqrt(r0*r0-(y1-y0)*(y1-y0))+x0;
    }
    p.first.x=x1;
    p.first.y=y1;
    p.second.x=x2;
    p.second.y=y2;
    return p;
}

bool isinside(needle p){
    double x=p.x,y=p.y,acc2=acc;
    if(x+acc2<0+wr||x-acc2>100-wr||y+acc2<0+wr||y-acc2>100-wr){
//    printf("(%f %f %f %f)\n",x-wr,y-wr,x-100+wr,y-100+wr);
//        printf(" outside");
        return true;
    }
    double d;
    for(int i=0;i<n;i++){
        d = sqrt((x-nd[i].x)*(x-nd[i].x)+(y-nd[i].y)*(y-nd[i].y));
        if(d+acc<nd[i].r){
//            printf(" %f\n",nd[i].r-d);
            return true;
        }
    }
    return false;
}

int main()
{
    int chk=0;
    double tmp;
    while(true){
        scanf("%d%d",&n,&w);
        if(n==0)
            return 0;
        ans = 0.0;
        for(int i=0;i<n;i++){
            scanf("%lf%lf%lf",&nd[i].x,&nd[i].y,&nd[i].h);
            //printf("%f",nd[i].x);
        }
        double lft=0.0,rgt=300.0,cur;
        while(lft<=rgt){
            cur = (lft+rgt)/2;
//            cur = 37.24602;
//            printf("%.2f: \n",cur);
            for(int i=0;i<n;i++){
                if(cur <= nd[i].h)
                    nd[i].r = cur;
                else{
                    tmp=cur-nd[i].h;
                    nd[i].r=sqrt(cur*cur-tmp*tmp);
                }
//                printf("\t%f %f %f\n",nd[i].x,nd[i].y,nd[i].r);
            }
            if(cur <= w){
                wr = cur;
            }
            else{
                tmp = cur-(double)w;
                wr=sqrt(cur*cur-tmp*tmp);
            }
//            printf(" %f] \n",wr);
            chk=0;
            for(int i=0;i<n;i++){
                for(int j=i+1;j<n;j++){
                    pnt = get_intersect(i,j);
                    if( (!isinside(pnt.first)) || (!isinside(pnt.second)) ){
//                        printf(" %d %d ",i,j);
                        chk=1;
                        break;
                    }

                }
                for(int L=1;L<=4;L++){
                    pnt = get_wallIntersect(i,wr,L);
                    if( (!isinside(pnt.first)) || (!isinside(pnt.second)) ){
//                        printf(" %d %d ",i,j);
                        chk=1;
                        break;
                    }
                }
                if(chk)
                    break;
            }
//            if(chk==0)
//                printf("==%f\n",cur);
            if(!chk){
                dmp.x = 0.0+wr; dmp.y = 0.0+wr;
                chk = chk || (!isinside(dmp));
                dmp.x = 0.0+wr; dmp.y = 100.0-wr;
                chk = chk || (!isinside(dmp));
                dmp.x = 100.0-wr; dmp.y = 0.0+wr;
                chk = chk || (!isinside(dmp));
                dmp.x = 100.0-wr; dmp.y = 100.0-wr;
                chk = chk || (!isinside(dmp));
            }
            if(chk){
                ans = cur;
                lft = cur+acc;
            }
            else{
                rgt = cur-acc;
            }
        }
        printf("%.5f\n",ans);
    }
}


```