P4047 [jsoi2010] tribal Division

P4047 [JSOI2010] Tribal Division （ Real number bisection avoids accuracy problems , Final square ）

---

Want to rush down 100 green

The question is MST, After reading it, I directly thought of two points .

I can't even read the solution MST

$BUT$ I seem to know that sometimes I can't think about two-point answers .

The distance between the two tribes is mid , Judge whether it can be satisfied n Two points are divided into k Share ？

First ： There are two stages , The answer can be divided into two parts .

My idea is , Yes k Share , What does each have ？ And then I thought about it and looked it up , Yes k Elements . from n One of the elements k individual , Then let other points and this k A comparison , Choose whichever you are close to .

What a genius idea The complexity is no more . Then I won't think .

---

Look at the explanation , People think like this . From scratch , There was nothing at first , If the distance between two points is less than mid Just merge , Finally, look up the representative elements and k The relationship between .

The problem with my thinking is , My judgment is not directly used mid！

then I TM The return value of two points is also wrong

When cnt （ Union checking set fa[i]==i） The number of Less than k when , It means the distance is too big , Otherwise, the distance is too small .

therefore : {cnt>=k, l = mid;} else r = mid;

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <sstream>
#define pb push_back 
#define in insert
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo_(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;

template<typename T>
ostream& operator<<(ostream& os,const vector<T>&v){
    for(int i=0,j=0;i<v.size();i++,j++)if(j>=5){
    j=0;puts("");}else os<<v[i]<<" ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>&v){
    for(auto c:v)os<<c<<" ";return os;}

typedef pair<int,int>PII;
typedef pair<long,long>PLL;

typedef long long ll;
typedef unsigned long long ull; 
const int N=1e5+10,M=1e5+10;
int n,k;
int fa[N];
int find(int x){
    
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}
struct Node{
    
	int l,r;
}node[1100];

double dist(Node x,Node y){
    
	return (x.l-y.l)*(x.l-y.l)+(x.r-y.r)*(x.r-y.r);
}

bool ck(double mid){
    
	fo(i,1,n)fa[i]=i;
	int cnt = 0;
	fo(i,1,n){
    
		fo(j,i+1,n){
    
			if(dist(node[i],node[j])<=mid)
				fa[find(j)]=find(i);
		}
	}
	fo(i,1,n)if(fa[i]==i)cnt++;
	return cnt>=k;
}

void solve(){
    
	cin>>n>>k;
	fo(i,1,n){
    
		cin>>node[i].l>>node[i].r;
	}
	double l = 0 , r = 1e9;
	while(r-l>1e-4){
    
		double mid = (l+r)/2;
		// debug(mid);
		if(ck(mid)){
    
			l = mid;
		}
		else {
    
			r = mid;
		}
	}
	printf("%.2lf",sqrt(l));
}

int main()
{
    
	solve();
	return 0;
}