Zombie Blast

#include<bits/stdc++.h>
using namespace std;

#define sc( x ) scanf( "%d" , &x )
#define REP( i , n ) for( int i = 0 ; i < n ; ++i )
#define clr( t , val ) memset( t , val , sizeof( t ) )

#define pb push_back

#define N 2000

typedef long long ll;
typedef long long ntype;
const ntype sentry = numeric_limits<ntype>::max();

struct point {
    ntype x, y;
    point(ntype xx = 0, ntype yy = 0) : x(xx), y(yy) {}
};
bool operator==(const point &a, const point &b){
    return a.x == b.x && a.y == b.y;
}
bool on_x(const point &a, const point &b){
    return a.x < b.x;
}
bool on_y(const point &a, const point &b){
    return a.y < b.y;
}
ntype pdist2(const point &a, const point &b){
    ntype dx = a.x-b.x, dy = a.y-b.y;
    return dx*dx + dy*dy;
}
struct bbox{
    ntype x0, x1, y0, y1;
    bbox() : x0(sentry), x1(-sentry), y0(sentry), y1(-sentry) {}
    void compute(const vector<point> &v) {
        for (int i = 0; i < v.size(); ++i) {
            x0 = min(x0, v[i].x);   x1 = max(x1, v[i].x);
            y0 = min(y0, v[i].y);   y1 = max(y1, v[i].y);
        }
    }
    ntype distance(const point &p) {
        if (p.x < x0) {
            if (p.y < y0)       return pdist2(point(x0, y0), p);
            else if (p.y > y1)  return pdist2(point(x0, y1), p);
            else                return pdist2(point(x0, p.y), p);
        }
        else if (p.x > x1) {
            if (p.y < y0)       return pdist2(point(x1, y0), p);
            else if (p.y > y1)  return pdist2(point(x1, y1), p);
            else                return pdist2(point(x1, p.y), p);
        }
        else {
            if (p.y < y0)       return pdist2(point(p.x, y0), p);
            else if (p.y > y1)  return pdist2(point(p.x, y1), p);
            else                return 0;
        }
    }
};
struct kdnode {
    bool leaf;
    point pt;
    bbox bound;

    kdnode *first, *second;

    kdnode() : leaf(false), first(0), second(0) {}
    ~kdnode() { if (first) delete first; if (second) delete second; }

    ntype intersect(const point &p) {
        return bound.distance(p);
    }

    void construct(vector<point> &vp)
    {
        bound.compute(vp);
        if (vp.size() == 1) {
            leaf = true;
            pt = vp[0];
        }
        else {
            if (bound.x1-bound.x0 >= bound.y1-bound.y0)
                sort(vp.begin(), vp.end(), on_x);
            else
                sort(vp.begin(), vp.end(), on_y);
            int half = vp.size()/2;
            vector<point> vl(vp.begin(), vp.begin()+half);
            vector<point> vr(vp.begin()+half, vp.end());
            first = new kdnode();   first->construct(vl);
            second = new kdnode();  second->construct(vr);
        }
    }
};
struct kdtree{
    kdnode *root;
    kdtree(const vector<point> &vp) {
        vector<point> v(vp.begin(), vp.end());
        root = new kdnode();
        root->construct(v);
    }
    ~kdtree() { delete root; }
    ntype search(kdnode *node, const point &p){
        if (node->leaf) {
                return pdist2(p, node->pt);
        }

        ntype bfirst = node->first->intersect(p);
        ntype bsecond = node->second->intersect(p);

        if (bfirst < bsecond) {
            ntype best = search(node->first, p);
            if (bsecond < best)
                best = min(best, search(node->second, p));
            return best;
        }
        else {
            ntype best = search(node->second, p);
            if (bfirst < best)
                best = min(best, search(node->first, p));
            return best;
        }
    }
    ntype nearest(const point &p) {
        return search(root, p);
    }
};
char S[ N + 5 ][ N + 5 ];
int main(){

    int cases , n , m;
    sc( cases );
    REP( tc , cases ){
        sc( m ) , sc( n );
        REP( i , n ) scanf( "%s" , S[ i ] );
        vector<point> vp;
        REP( i , n )REP( j , m )
            if( S[ i ][ j ] == 'M' ){
                vp.pb( point( i , j ) );
            }
        kdtree tree(vp);
        ll ans = 0;
        REP( i , n )REP( j , m )if( S[ i ][ j ] == 'Z' ){
            ans = max( ans , tree.nearest( point( i , j ) ) );
        }
        printf( "%.10f\n" , (double)sqrt( ans ) );
    }

    /*
    vector<point> vp;
    for (int i = 0; i < 4000000; ++i) {
        vp.push_back(point(rand()%100000, rand()%100000));
    }
    kdtree tree(vp);

    // query some points
    for (int i = 0; i < 4000000; ++i) {
        point q(rand()%100000, rand()%100000);
        cout << "Closest squared distance to (" << q.x << ", " << q.y << ")"
             << " is " << tree.nearest(q) << endl;
    }
    */
}