题解

期中考前吃一道水题放松一下。

注意到本题 $n$ 很小，随便乱搞都能过。

注意到 $d$ 满足单调性，考虑二分答案。

我们两两枚举，如果长度小于等于 $d$ 就说明可以传递，在一个连通块上。

最后只需要判断连通块的数量是否小于等于 $m$ 即可。

注意没有卫星和只有一个卫星是等价的。所以当 $m=0$ 时可以当做 $m=1$ 看待。

#include <iostream>
#include <cstdio>
#include <vector>
#include <iomanip>
namespace cjdst{

	template <typename T>
	class Fenwick_Tree{
		std::vector <T> tr;
		int n;

		public:

		Fenwick_Tree(){}
		Fenwick_Tree(int n, std::vector <T> a){
			tr.resize(n + 5, 0);
			this -> n = n;
			for(int i = 1; i <= n; i++){
				tr[i] += a[i];
				if(i + (i & (-i)) <= n){
					tr[i + (i & (-i))] += tr[i];
				}
			}
		}
		void modify(int idx, T val){
			for(int i = idx; i <= n; i += (i & (-i))) tr[i] += val;
		}
		T query(int idx){
			T ans = 0;
			for(int i = idx; i; i -= (i & (-i))) ans += tr[i];
			return ans;
		}
	};

	template <typename T>
	class Segtree{
		std::vector <T> tr;
		std::vector <int> left, right;
		std::vector <T> lazytag;
		void push_up(int u){
			tr[u] = tr[u << 1] + tr[u << 1 | 1];
		}
		void push_down(int u){
			tr[u << 1] += (right[u << 1] - left[u << 1] + 1) * lazytag[u];
			tr[u << 1 | 1] += (right[u << 1 | 1] - left[u << 1 | 1] + 1) * lazytag[u];
			lazytag[u << 1] += lazytag[u];
			lazytag[u << 1 | 1] += lazytag[u];
			lazytag[u] = 0;
		}
		void build(int u, int l, int r, std::vector <T> &a){
			left[u] = l, right[u] = r;
			if(l == r){
				tr[u] = a[l];
				return;
			}
			int mid = (l + r) >> 1;
			build(u << 1, l, mid, a);
			build(u << 1 | 1, mid + 1, r, a);
			push_up(u);
		}
		void _modify(int u, int l, int r, T val){
			if(left[u] >= l && right[u] <= r){
				tr[u] += (right[u] - left[u] + 1) * val;
				lazytag[u] += val;
				return;
			}
			push_down(u);
			if(right[u << 1] >= l) _modify(u << 1, l, r, val);
			if(left[u << 1 | 1] <= r) _modify(u << 1 | 1, l, r, val);
			push_up(u);
		}
		T _query(int u, int l, int r){
			if(left[u] >= l && right[u] <= r){
				return tr[u];
			}
			push_down(u);
			T ans = 0;
			if(right[u << 1] >= l) ans += _query(u << 1, l, r);
			if(left[u << 1 | 1] <= r) ans += _query(u << 1 | 1, l, r);
			return ans;
		}

		public:

		Segtree(){}
		Segtree(int n, std::vector <T> a){
			tr.resize(n * 4 + 5);
			left.resize(n * 4 + 5);
			right.resize(n * 4 + 5);
			lazytag.resize(n * 4 + 5);
			build(1, 1, n, a);
		}
		void modify(int l, int r, T val){
			_modify(1, l, r, val);
		}
		T query(int l, int r){
			return _query(1, l, r);
		}
	};
	
	class dsu{
		std::vector <int> father, siz;
		
		public:
		
		int n, unions;
		dsu(){
			n = 0;
		}
		dsu(int n){
			this -> n = n;
			unions = n;
			father.resize(n + 5, 0);
			siz.resize(n + 5, 1);
			for(int i = 1; i <= n; i++){
				father[i] = i;
			}
		}
		int find(int n){
			return (father[n] == n ? n : father[n] = find(father[n]));
		}
		void merge(int x, int y){
			x = find(x), y = find(y);
			if(x == y) return;
			if(siz[x] < siz[y]) std::swap(x, y);
			siz[x] += siz[y];
			father[y] = x;
			unions--;
		}
	};

	void init(){
		std::ios::sync_with_stdio(0);
		std::cin.tie(0);
		std::cout.tie(0);
	}

	typedef long long ll;
	typedef unsigned long long ull;
	typedef std::pair <int, int> pii;
	typedef std::pair <ll, ll> pll;
	
	bool check(double mid, int n, int m, std::vector <int> &a, std::vector <int> &b){
		dsu u(n);
		for(int i = 1; i <= n; i++){
			for(int j = i + 1; j <= n; j++){
				int x = a[i] - a[j];
				int y = b[i] - b[j];
				if(x * x + y * y - mid * mid <= (-1e-9)) u.merge(i, j);
			}
		}
		return u.unions <= m;
	}

	void solve(){
		std::vector <int> a, b;
		int n, m;
		std::cin >> n >> m;
		if(!m) m = 1;
		a.resize(n + 5, 0);
		b.resize(n + 5, 0);
		for(int i = 1; i <= n; i++){
			std::cin >> a[i] >> b[i];
		}
		double l = 0, r = 1e9;
		while(r - l > (1e-9)){
			double mid = (l + r) / 2;
			if(check(mid, n, m, a, b)) r = mid;
			else l = mid;
		}
		std::cout << std::setprecision(2) << std::fixed << l << '\n';
	}
}


int main(){
	cjdst::init();
	int T = 1;
	// std::cin >> T;
	for(int _ = 1; _ <= T; _++){
		cjdst::solve();
	}
	std::cout.flush();

	return 0;
}

时间复杂度：$O(n^2\alpha(n)\log V)$。

诶不对这个好像可以用 MST 求解优化成 $O(n^2\log n)$？算了不管了。