센서와 벽을 노드 취급하고, 간선은 두 노드 사이에 들어갈 수 있는 원의 최대 지름으로 합시다. $O(N^2)$번의 연산이 요구되므로 N<=1,000인 이 문제에서는 무리없이 해결 가능합니다.
이 때, 경로가 존재하지 않을 때까지 두 노드 사이를 차단한다고 생각해봅시다. 경로가 하나라도 존재할 때 차단되지 않은 간선의 가중치 최솟값이 그 때 존재하는 경로만을 고려할 때의 답이라고 할 수 있습니다. 그렇다면 이런 가중치의 최솟값을 최대화하면 되는데, 이는 간선을 가중치 기준으로 정렬하고 가중치가 작은 것부터 차단해가며 완전히 모든 경로가 존재하지 않을 때 차단한 간선의 가중치를 구하면 이것이 전체 문제의 해답임을 알 수 있습니다.
간선이 $O(N^2)$개이므로 이를 정렬하는 것에 대해 TC당 시간복잡도가 의존적입니다. 따라서 TC 당 $O(N^2 log N)$, 전체 시간 복잡도 $O(T N^2 log N)$이므로 충분히 해결할 수 있습니다.
구현에서 실수 오차와 오버플로우 등 조금 까다로운 처리가 존재해 디버깅 후에는 충분히 화가 날 수 있습니다.
#include<bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
const int nmax=2010;
class UF{
public:
int par[nmax];
UF(){
memset(par,-1,sizeof(par));
}
int fnd(int u){
if(par[u]<0)return u;
return par[u]=fnd(par[u]);
}
int mer(int u,int v){
u=fnd(u);v=fnd(v);
if(u==v)return 0;
par[v]+=par[u];
par[u]=v;
return 1;
}
};
pii operator-(pii x,pii y){
return pii(x.first-y.first,x.second-y.second);
}
double edist(pii x,pii y){
pii z=x-y;
return sqrt((long long)z.first*z.first+(long long)z.second*z.second)+1e-8;
}
struct dot{
pii p;
int r;
dot(pii a=pii(0,0),int b=0):p(a),r(b){}
};
struct edge{
int a,b;
double l;
edge(int x,int y,double z):a(x),b(y),l(z){}
bool operator<(const edge& e) const{
return l<e.l;
}
};
UF uf;
vector<dot> dv;
vector<edge> ev;
void TC(){
dv.clear();
ev.clear();
memset(uf.par,-1,sizeof(uf.par));
int w,n;
scanf("%d%d",&w,&n);
ev.emplace_back(n,n+1,w);
for(int i=0;i<n;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
dv.emplace_back(pii(a,b),c);
for(int j=0;j<i;j++){
double d=edist(dv[i].p,dv[j].p)-dv[i].r-dv[j].r;
ev.emplace_back(i,j,max(d,(double)0));
}
ev.emplace_back(i,n,max((double)a-c,(double)0));
ev.emplace_back(i,n+1,max((double)w-a-c,(double)0));
}
sort(ev.begin(),ev.end());
for(int i=0;i<ev.size();i++){
if(!uf.mer(ev[i].a,ev[i].b))continue;
if(uf.fnd(n)==uf.fnd(n+1)){
if(ev[i].l==0){
printf("0\n");
return;
}
printf("%.6f\n",ev[i].l*0.5);
return;
}
}
}
int32_t main(void){
int tc;
scanf("%d",&tc);
while(tc--){
TC();
}
}