自动搬运

查看原文

来自洛谷，原作者为

	pikiuk “Back like I never left!”

搬运于2025-08-24 22:33:45，当前版本为作者最后更新于2023-08-31 19:39:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

分享一种确定性做法。

首先对于 $d$ 二分，问题转化为判定性问题。

可以发现，若一个县的大小大于等于 $k$，那么他一定合法，理由是一定能找到两个余数互补的城市（鸽巢原理）。

考察一个边长为 $d\times d$ 的矩形，我们可以发现，若其中有不少于 $4k$ 个点，那么 $d$ 一定合法。证明可以同样是鸽巢原理，具体的，我们把一个矩形划分为四个子矩形，那么每个子矩形内的点一定可以构成一个县，且至少存在一个子矩形内的点多于 $k$ 个。

我们对点的 $x$ 轴扫描线，维护以当前点为右边界中点的矩形，并把当前点向当前矩形内所有点连边，可以用 set 维护，由上述分析发现，每个点的出边不超过 $k$ 条。

连边结束后，对现有连通块做背包即可，单次检验时间复杂度是 $\mathcal{O}(nk)$。

#include<bits/stdc++.h>
#define int long long
using namespace std;
using i64 = long long;
const int N = 5e4 + 7, K = 37;
int f[N][K], n, k, col[N], cnt;
vector<int> e[N], vec;
struct Point {
	int x, y, z;
} p[N];
struct cmp {
	bool operator () (const int &u, const int &v) const {
		return ((p[u].y == p[v].y) ? u > v : p[u].y < p[v].y);
	}
};
set <int, cmp> st;
void add (int &x, int y) { x = (x + y) >= k ? x + y - k : x + y; }
i64 dis (int u, int v) {
	return 0ll + 1ll * (p[u].x - p[v].x) * (p[u].x - p[v].x) + 1ll * (p[u].y - p[v].y) * (p[u].y - p[v].y);
}
void dfs (int u) {
	col[u] = cnt; vec.push_back (p[u].z);
	for (auto v : e[u]) if (! col[v]) dfs (v);
}
bool subset () {
	int m = (int) vec.size ();
	if (m > k) return true;
	for (int i = 1; i < k; i ++) f[m][i] = 0;
	f[m][0] = 1;
	for (int i = m - 1; ~i; i --) {
		for (int j = 0; j < k; j ++) {
			f[i][j] = f[i + 1][j];
			f[i][j] |= f[i + 1][(vec[i] + j) % k];
		}
		if (f[i + 1][vec[i]]) return true;
	}
	return false;
}
bool check (i64 d) {
	int sqrtd = (double) (sqrt (d) + 1);
	for (int i = 1; i <= n; i ++) e[i].clear (), col[i] = 0;
	cnt = 0; st.clear ();
	for (int i = 1, j = 1; i <= n; i ++) {
		for (; p[i].x - p[j].x > sqrtd and j <= i; ) 
			st.erase (j ++);
		if (st.empty ()) { st.insert (i); continue; }
	
		p[n + 1] = {0, p[i].y - sqrtd, 0}; int res = 0;
		for (auto it = st.lower_bound (n + 1); it != st.end (); it ++) {
			auto k = *it;
			if (p[k].y - p[i].y > sqrtd) break;
			if (++ res >= 4 * k) return true;
			if (dis (i, k) <= d) e[i].push_back (k), e[k].push_back (i);
		}
		st.insert (i);
	}
	for (int i = 1; i <= n; i ++) {
		vec.clear ();
		if (col[i]) continue;
		++ cnt, dfs (i);
		if (subset ()) return true;
	}
	return false;
}
signed main () {
	cin >> n >> k;
	for (int i = 1; i <= n; i ++) {
		cin >> p[i].x >> p[i].y >> p[i].z;
		p[i].z %= k;
	}
	sort (p + 1, p + n + 1, [&] (const Point &u, const Point &v) {
		return u.x == v.x ? u.y < v.y : u.x < v.x;
	});
	i64 l = 0, r = 1e18, ans = -1;
	while (l <= r) {
		i64 mid = (l + r) >> 1;
		if (check (mid)) r = mid - 1, ans = mid;
		else l = mid + 1;
	}	
	cout << fixed << setprecision (3) << sqrt (ans);
}