HDU 3585 maximum shortest distance

The question ： Yes n A little bit . selection k A little bit （k> = 2）, And here it is k The nearest two points in the point are the farthest .

Answer key ： Two points + The biggest group
The nearest farthest , Lean on two points .

Because the nearest two points are connected by k Points form the least edge weight in a complete graph , Then the other edges must be greater than or equal to this value , Then we can divide the answer by two .

For the two-point mid, Each time will be greater than or equal to mid Connect the edge of the , Then run the largest regiment （ Only when dots are directly connected can the shortest edge weight be guaranteed , If it is not a complete graph, there must be less than mid The edge of ）, If the number of knots of the largest clique is greater than or equal to k, Then the number of nodes of the largest clique is equal to k, And the minimum edge weight is greater than or equal to mid The children of .

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<fstream>
#include<set>
#include<map>
#include<sstream>
#include<iomanip>
#define ll long long
#define pii pair<int, int>
using namespace std;
struct node {
    
	double x, y;
}p[55];
double dis(node a, node b) {
    
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
int n, k;
struct node1 {
    
	int x, y;
	double dis;
	bool operator<(const node1 a)const {
    
		return dis < a.dis;
	}
}edge[5555];
/*  The biggest group  =  Make up a picture G The maximum number of independent sets of  ———> Maximum number of independent sets  =  Make up a picture G' The biggest group  */
#define N 55
int mx;// Maximum number of cliques ( To initialize to 0)
int x[N], tuan[N];
int can[N][N];//can[i] Indicates that the selected i A point must be in the largest clique and may be added to the node set of the largest clique 
int num[N];//num[i] Indicates by node i To the node n The number of knots of the largest group formed 
bool g[N][N];// Adjacency matrix ( from 1 Start )
bool dfs(int tot, int cnt) {
    
	int i, j, k;
	if (tot == 0) {
    
		if (cnt > mx) {
    
			mx = cnt;
			for (i = 0; i < mx; i++) tuan[i] = x[i];
			return true;
		}
		return false;
	}
	for (i = 0; i < tot; i++) {
    
		if (cnt + (tot - i) <= mx)return false;
		if (cnt + num[can[cnt][i]] <= mx)return false;
		k = 0;
		x[cnt] = can[cnt][i];
		for (j = i + 1; j < tot; j++) {
    
			if (g[can[cnt][i]][can[cnt][j]]) can[cnt + 1][k++] = can[cnt][j];
		}
		if (dfs(k, cnt + 1))return false;
	}
	return false;
}
void MaxTuan() {
    
	int i, j, k;
	mx = 1;
	for (i = n; i >= 1; i--) {
    
		k = 0;
		x[0] = i;
		for (j = i + 1; j <= n; j++) {
    
			if (g[i][j]) can[1][k++] = j;
		}
		dfs(k, 1);
		num[i] = mx;
	}
}
int nu;
bool check(double mid) {
    
	int pos = lower_bound(edge + 1, edge + nu + 1, node1{
     0, 0, mid }) - edge;
	memset(g, 0, sizeof(g));
	for (int i = pos; i <= nu; i++) {
    
		g[edge[i].x][edge[i].y] = g[edge[i].y][edge[i].x] = 1;
	}
	mx = 0;
	MaxTuan();
	if (num[1] >= k) return true;
	else return false;
}
int main() {
    
	while (~scanf("%d%d", &n, &k)) {
    
		for (int i = 1; i <= n; i++) scanf("%lf%lf", &p[i].x, &p[i].y);
		nu = 0;
		double l = 0, r = 0;
		for (int i = 1; i <= n; i++) {
    
			for (int j = i + 1; j <= n; j++) {
    
				double di = dis(p[i], p[j]);
				edge[++nu] = {
     i, j, di };
				r = max(r, di);
			}
		}
		sort(edge + 1, edge + nu + 1);
		double mid;
		while (r - l > 1e-6) {
    
			mid = (l + r) / 2;
			if (check(mid))l = mid;
			else r = mid;
		}
		printf("%.2f\n", mid);
	}
	return 0;
}