#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(a); (i)<(b); ++(i))
#define rFor(i, a, b) for(int (i)=(a)-1; (i)>=(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef pair<int, int> pii;
typedef pair<pii, lint> ppl;
typedef pair<lint, lint> pll;
typedef complex<double> xy_t;
typedef pair<xy_t, xy_t> Line;
typedef pair<xy_t, double> Circle;
typedef vector<lint> poly;

const double eps = 1e-9;

double dot(xy_t a, xy_t b){
    return (conj(a) * b).real();
}

double cross(xy_t a, xy_t b){
    return (conj(a) * b).imag();
}

xy_t proj(xy_t a1, xy_t a2, xy_t p){
    return a1 + dot(a2-a1, p-a1)/norm(a2-a1) * (a2-a1);
}

double dist_LP(xy_t a1, xy_t a2, xy_t p){
    return abs(proj(a1, a2, p) - p);
}

xy_t inter_LL(xy_t a1, xy_t a2, xy_t b1, xy_t b2){
    xy_t a = a2 - a1; xy_t b = b2 - b1;
    return a1 + a * cross(b, b1-a1) / cross(b, a);
}

pair<xy_t, xy_t> inter_LC(xy_t a1, xy_t a2, xy_t c, double r){
    pair<xy_t, xy_t> ps = make_pair(xy_t(-1, -1), xy_t(-1, -1));
    xy_t ft = proj(a1, a2, c);
    if(r*r + eps < norm(ft - c)) return ps;

    xy_t dir = sqrt(max(r*r - norm(ft-c), 0.0)) / abs(a2-a1) * (a2-a1);
    ps.fi = ft + dir;
    if(abs(r*r - norm(ft-c)) >= eps) ps.se = ft - dir;
    return ps;
}

pair<xy_t, xy_t> inter_CC(xy_t a, double ar, xy_t b, double br){
    pair<xy_t, xy_t> ps = make_pair(xy_t(-1, -1), xy_t(-1, -1));
    xy_t ab = b-a;
    double d = abs(ab);
    double crL = (norm(ab) + ar*ar - br*br) / (2*d);
    if(abs(d) < eps || ar < abs(crL)) return ps;

    xy_t abN = ab * xy_t(0, sqrt(ar*ar - crL*crL) / d);
    xy_t cp = a + crL/d * ab;
    ps.fi = (cp + abN);
    if(abs(norm(abN)) >= eps) ps.se = cp - abN;
    return ps;
}

double getd(double r, double h){
    if(r <= h) return r;
    return sqrt(2*r*h - h*h);
}

int n;
double w, x[110], y[110], h[110];
Line L[5];
Circle C[15];
vector<xy_t> P;

bool cover_check(xy_t p){
    double d = L[0].fi.real();
    double px = p.real(), py = p.imag();
    if(px+eps < d || px > 100-d+eps || py+eps < d || py > 100-d+eps){
        return false;
    }

    rep(i, n)if(abs(p-C[i].fi)+eps < C[i].se){
        return false;
    }

    return true;
}

bool check(double mid){
    P.clear();
    double d = getd(mid, w);
    P.emplace_back(d, d);
    P.emplace_back(d, 100-d);
    P.emplace_back(100-d, d);
    P.emplace_back(100-d, 100-d);
    L[0] = make_pair(P[0], P[1]);
    L[1] = make_pair(P[0], P[2]);
    L[2] = make_pair(P[1], P[3]);
    L[3] = make_pair(P[2], P[3]);

    rep(i, n){
        double r = getd(mid, h[i]);
        C[i] = Circle(xy_t(x[i], y[i]), r);
    }

    rep(i, 4)rep(j, n){
        auto ps = inter_LC(L[i].fi, L[i].se, C[j].fi, C[j].se);
        if(ps.fi.real() + eps >= 0) P.push_back(ps.fi);
        if(ps.se.real() + eps >= 0) P.push_back(ps.se);
    }

    rep(i, n)For(j, i+1, n){
        auto ps = inter_CC(C[i].fi, C[i].se, C[j].fi, C[j].se);
        if(ps.fi.real() + eps >= 0) P.push_back(ps.fi);
        if(ps.se.real() + eps >= 0) P.push_back(ps.se);
    }

    for(auto p: P)if(cover_check(p)){
        return true;
    }

    return false;
}

int main(){
    while(scanf("%d%lf", &n, &w) && n){
        rep(i, n) scanf("%lf%lf%lf", &x[i], &y[i], &h[i]);

        double low = 0, high = 150;
        rep(loop, 100){
            double mid = (high + low) / 2;
            (check(mid) ? low : high) = mid;
        }

        printf("%.5lf\n", low);
    }
}

### Prompt

Please create a solution in Cpp to the following problem:

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 <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(a); (i)<(b); ++(i))
#define rFor(i, a, b) for(int (i)=(a)-1; (i)>=(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef pair<int, int> pii;
typedef pair<pii, lint> ppl;
typedef pair<lint, lint> pll;
typedef complex<double> xy_t;
typedef pair<xy_t, xy_t> Line;
typedef pair<xy_t, double> Circle;
typedef vector<lint> poly;

const double eps = 1e-9;

double dot(xy_t a, xy_t b){
    return (conj(a) * b).real();
}

double cross(xy_t a, xy_t b){
    return (conj(a) * b).imag();
}

xy_t proj(xy_t a1, xy_t a2, xy_t p){
    return a1 + dot(a2-a1, p-a1)/norm(a2-a1) * (a2-a1);
}

double dist_LP(xy_t a1, xy_t a2, xy_t p){
    return abs(proj(a1, a2, p) - p);
}

xy_t inter_LL(xy_t a1, xy_t a2, xy_t b1, xy_t b2){
    xy_t a = a2 - a1; xy_t b = b2 - b1;
    return a1 + a * cross(b, b1-a1) / cross(b, a);
}

pair<xy_t, xy_t> inter_LC(xy_t a1, xy_t a2, xy_t c, double r){
    pair<xy_t, xy_t> ps = make_pair(xy_t(-1, -1), xy_t(-1, -1));
    xy_t ft = proj(a1, a2, c);
    if(r*r + eps < norm(ft - c)) return ps;

    xy_t dir = sqrt(max(r*r - norm(ft-c), 0.0)) / abs(a2-a1) * (a2-a1);
    ps.fi = ft + dir;
    if(abs(r*r - norm(ft-c)) >= eps) ps.se = ft - dir;
    return ps;
}

pair<xy_t, xy_t> inter_CC(xy_t a, double ar, xy_t b, double br){
    pair<xy_t, xy_t> ps = make_pair(xy_t(-1, -1), xy_t(-1, -1));
    xy_t ab = b-a;
    double d = abs(ab);
    double crL = (norm(ab) + ar*ar - br*br) / (2*d);
    if(abs(d) < eps || ar < abs(crL)) return ps;

    xy_t abN = ab * xy_t(0, sqrt(ar*ar - crL*crL) / d);
    xy_t cp = a + crL/d * ab;
    ps.fi = (cp + abN);
    if(abs(norm(abN)) >= eps) ps.se = cp - abN;
    return ps;
}

double getd(double r, double h){
    if(r <= h) return r;
    return sqrt(2*r*h - h*h);
}

int n;
double w, x[110], y[110], h[110];
Line L[5];
Circle C[15];
vector<xy_t> P;

bool cover_check(xy_t p){
    double d = L[0].fi.real();
    double px = p.real(), py = p.imag();
    if(px+eps < d || px > 100-d+eps || py+eps < d || py > 100-d+eps){
        return false;
    }

    rep(i, n)if(abs(p-C[i].fi)+eps < C[i].se){
        return false;
    }

    return true;
}

bool check(double mid){
    P.clear();
    double d = getd(mid, w);
    P.emplace_back(d, d);
    P.emplace_back(d, 100-d);
    P.emplace_back(100-d, d);
    P.emplace_back(100-d, 100-d);
    L[0] = make_pair(P[0], P[1]);
    L[1] = make_pair(P[0], P[2]);
    L[2] = make_pair(P[1], P[3]);
    L[3] = make_pair(P[2], P[3]);

    rep(i, n){
        double r = getd(mid, h[i]);
        C[i] = Circle(xy_t(x[i], y[i]), r);
    }

    rep(i, 4)rep(j, n){
        auto ps = inter_LC(L[i].fi, L[i].se, C[j].fi, C[j].se);
        if(ps.fi.real() + eps >= 0) P.push_back(ps.fi);
        if(ps.se.real() + eps >= 0) P.push_back(ps.se);
    }

    rep(i, n)For(j, i+1, n){
        auto ps = inter_CC(C[i].fi, C[i].se, C[j].fi, C[j].se);
        if(ps.fi.real() + eps >= 0) P.push_back(ps.fi);
        if(ps.se.real() + eps >= 0) P.push_back(ps.se);
    }

    for(auto p: P)if(cover_check(p)){
        return true;
    }

    return false;
}

int main(){
    while(scanf("%d%lf", &n, &w) && n){
        rep(i, n) scanf("%lf%lf%lf", &x[i], &y[i], &h[i]);

        double low = 0, high = 150;
        rep(loop, 100){
            double mid = (high + low) / 2;
            (check(mid) ? low : high) = mid;
        }

        printf("%.5lf\n", low);
    }
}

```