Will Indiana Jones Get There? AC - Live Archive 2613

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <stdlib.h>
#include <math.h>
using namespace std;

inline int sq(int x) {
    return x*x;
}

int dInter(int al, int ar, int bl, int br) {
    if (al>bl) swap(al, bl), swap(ar, br);

    if (al<=bl && ar>=bl) return 0;
    return bl-ar;
}

struct seg {
    int l,r,b,t;

    int dist2(seg& a) {
        int d=0;

        d=sq(dInter(this->l, this->r,
            a.l, a.r));
        d+=sq(dInter(this->b, this->t,
            a.b, a.t));
        return d;
    }

    void read() {
        int x,y,len;
        scanf("%d %d %d", &x,&y,&len);
        this->l=this->r=x;
        this->b=this->t=y;

        if (len<0) this->t-=len;
        else this->r+=len;
    }
};

const int inf =0x3f3f3f3f;

int n;
int g[1010][1010];
seg s[1010];
int b,e;
bool mark[1010];

void dfs(int v, int maxEdge) {
    mark[v]=true;

    for (int i=0; i<n; i++)
        if (g[v][i]<=maxEdge && !mark[i])
            dfs(i,maxEdge);
}

int main() {
    while (1) {
        scanf("%d", &n);
        if (!n) break;

        for (int i=0; i<n; i++)
            s[i].read();

        memset(g,0x3f,sizeof(g));

        for (int i=0; i<n; i++)
            g[i][i]=0;

        for (int i=0; i<n; i++)
            for (int j=i+1; j<n; j++)
                g[i][j]=g[j][i]=s[i].dist2(s[j]);

        for (b=0, e=inf-10; b<e; ) {
            int mid=(b+e)/2;
            memset(mark,0,sizeof(mark));
            dfs(0,mid);

            if (mark[1]) e=mid;
            else b=mid+1;
        }

        printf("%.2lf\n", sqrt(b));
    }
    return 0;
}