题意：给定一些点，要把这些点分为k个部落，问最近两个部落间的最远距离是多少。
解法：二分答案+并查集检测鸭！二分的时候要注意精度问题噢，eps开到1e-3会有一个点过不去。开始看错题意想半天。
代码：
#include <algorithm> #include <iostream> #include <cstring> #include <vector> #include <cstdio> #include <queue> #include <cmath> #include <set> #include <map> #include<bitset> #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define _for(n,m,i) for (register int i = (n); i < (m); ++i) #define _rep(n,m,i) for (register int i = (n); i <= (m); ++i) #define lson rt<<1, l, mid #define rson rt<<1|1, mid+1, r #define PI acos(-1) #define eps 1e-4 #define rint register int #define F(x) ((x)/3+((x)%3==1?0:tb)) #define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2) using namespace std; typedef long long LL; typedef pair<LL, int> pli; typedef pair<int, int> pii; typedef pair<double, int> pdi; typedef pair<LL, LL> pll; typedef pair<double, double> pdd; typedef map<int, int> mii; typedef map<LL, int> mli; typedef map<char, int> mci; typedef map<string, int> msi; template<class T> void read(T &res) { int f = 1; res = 0; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { res = res * 10 + c - '0'; c = getchar(); } res *= f; } const int ne[8][2] = {1, 0, -1, 0, 0, 1, 0, -1, -1, -1, -1, 1, 1, -1, 1, 1}; const LL INF = 1e18; const int N = 1010; const LL Mod = 1e9+7; const int M = 110; int n, k; pdd p[N]; double tu[N][N]; double dis(pdd p1, pdd p2) { return sqrt((p1.first-p2.first)*(p1.first-p2.first) + (p1.second-p2.second)*(p1.second-p2.second)); } int f[N]; int Find(int x) { return f[x] == x ? x : f[x] = Find(f[x]); } int check(double x) { _rep(1, n, i) f[i] = i; int fi, fj; _rep(1, n, i) _for(1, i, j) { if(tu[i][j] >= x) continue; fi = Find(i); fj = Find(j); if(fi != fj) f[fi] = fj; } int cnt = 0; _rep(1, n, i) { if(Find(i) == i) ++cnt; } //cout << x << " " << cnt << endl; return cnt >= k; } int main() { scanf("%d%d", &n, &k); double mx = 0; _rep(1, n, i) { scanf("%lf%lf", &p[i].first, &p[i].second); _for(1, i, j) tu[i][j] = tu[j][i] = dis(p[i], p[j]), mx = max(mx, tu[i][j]); } double l = 0, r = mx, mid, ans = mx; while(r-l>eps) { mid = (l + r) / 2.0; if(check(mid)) ans = mid, l = mid; else r = mid; } printf("%.2lf\n", ans); return 0; }