- #include < cmath > #include < cstdio > #include < cctype > #include < cstring > #include < algorithm >
- using namespace std;
- const int MAXN = 1010;
- int n,
- k,
- cnt,
- tot;
- int x[MAXN],
- y[MAXN],
- fa[MAXN];
- struct node {
- int x,
- y;
- double dis;
- bool operator < (const node & a) const {
- return dis < a.dis;
- }
- };
- node e[MAXN * MAXN];
- inline void read(int & x) {
- int f = 1;
- register char c = getchar();
- for (x = 0; ! isdigit(c); c == ‘ - ‘ && (f = -1), c = getchar());
- for (; isdigit(c); x = x * 10 + c - 48, c = getchar());
- x = x * f;
- }
- inline double c(int i, int j) {
- return sqrt((double)(x[i] - x[j]) * (x[i] - x[j]) + (double)(y[i] - y[j]) * (y[i] - y[j]));
- }
- inline int find(int x) {
- if (x == fa[x]) return x;
- return fa[x] = find(fa[x]);
- }
- int hh() {
- // freopen("people.in","r",stdin);
- // freopen("people.out","w",stdout);
- read(n);
- read(k);
- for (int i = 1; i <= n; ++i) read(x[i]),
- read(y[i]),
- fa[i] = i;
- for (int i = 1; i <= n; ++i) for (int j = i + 1; j <= n; ++j) {
- e[++cnt].x = i;
- e[cnt].y = j;
- e[cnt].dis = c(i, j);
- }
- sort(e + 1, e + 1 + cnt);
- n = n - k + 1;
- for (int i = 1; i <= cnt; ++i) {
- int xx = find(e[i].x);
- int yy = find(e[i].y);
- if (xx != yy) {
- fa[xx] = yy; ++tot;
- if (tot == n) {
- printf("%.2lf\n", e[i].dis);
- goto END;
- }
- }
- }
- END: return 0;
- }
- int sb = hh();
- int main(int argc, char * *argv) {;
- }
来源: http://www.bubuko.com/infodetail-2294792.html