$\color{deeppink}link$

题意：给定 $n\in[1,5e4]$ 个点，点有坐标及点权，连一些边，使某一个连通块中，某些点权相加整除给定的 $k\in[1,30]$，最小化边权（即点之间的距离）最大值。

看到最小化最大值，第一时间想到二分。可以设定边界。 $l=0,r=10^8\sqrt{2}$

我们可以将 $n$ 个点每两个匹配，然后用一个并查集把联通的点维护下，判断可行性就用 01 背包，用 $f_{x,i}$ 表示 $x$ 的点集内有 $i$ 个人是否可行。

注意到 $i$ 可能十分大，但 $k$ 只有 $30$，且题目只要求整除 $k$，所以没必要把人数具体存下，只要存一个取模 $k$ 的值。$f_{x,0}=1$ 就代表可以整除

初始时 $f_{x,val_x}=1$，合并 $x$ 和 $y$ 就 $k^2$ 枚举下，把所有的 $f_{x,i}~\text{and}~f_{y,p-i}(p\in[0,2k])$ 或起来，合并到 $g_p$ 里面。

$g$ 是中间转移的数组，转移后把 $g$ 赋值给 $f_x$。

还有就是因为 $f_{x,0}$ 没值，要先用 $f_x$ 和 $f_y$ 把 $g$ 赋下初始值，就是 $g_i=f_{x,i}~\text{or}~f_{y,i}$。

这样做每个点对都枚举了一次，单次判断复杂度是 $O(n^2)$ 的，明显过不了。

考虑剪枝。先对所有点按横坐标排序，只枚举横坐标之差在二分的答案之内的，然后把已经在同一点集的点排除掉，找到可行的方案直接返回，就可以过了。

$code$

#include<bits/stdc++.h>
#define esp 1e-6
#define db double
using namespace std;
const int N=1e6+50;

struct node
{
	int x,y,val;
	
	friend bool operator<(node a,node b)
	{
		return a.x==b.x?a.y<b.y:a.x<b.x;
	}
}a[N];

int n,k,ro[N];
bool f[N][35];

db dis(int x,int y)
{
	return sqrt(1ll*(a[x].x-a[y].x)*(a[x].x-a[y].x)+1ll*(a[x].y-a[y].y)*(a[x].y-a[y].y));
}

int find(int x)
{
	return x==ro[x]?x:(ro[x]=find(ro[x]));
}

int check(db x)
{
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=k;j++)f[i][j]=0;
		ro[i]=i;f[i][a[i].val]=1;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			if(a[j].x-a[i].x>x)break;
			int ri=find(i),rj=find(j);
			if(dis(i,j)>x||ri==rj)continue;
			int g[65];memset(g,0,sizeof g);
			for(int l=0;l<=k;l++)if(f[ri][l])
			for(int r=0;r<=k;r++)if(f[rj][r])
			g[l+r]=1;
			for(int l=0;l<=k+k;l++)f[ri][l%k]|=g[l]|f[rj][l%k];
			ro[ri]=ro[rj]=ri;
			if(f[ri][0])return 1;
		}
	}
	return 0;
}

main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].x>>a[i].y>>a[i].val;
		a[i].val%=k;
	}
	sort(a+1,a+1+n);
	db l=0,r=2e8,ans=1919810;
	while(l<=r-esp)
	{
		db mid=(l+r)/2;
		if(check(mid))ans=mid,r=mid;
		else l=mid;
	}
	cout<<fixed<<setprecision(3)<<ans<<'\n';
}