Vol5

JSOI2010 Group
BZOJ1821

显然，我们可以二分最大的最小值，记为ans。

如果两个点之间的距离小于这个ans，也就是说这两个点必须被划进一个部落，则我们将这两个点置于一个集合中。

我们证明：在ans意义下，问题有解的充分必要条件是非空集合的数量大于等于k个。

必要性是显然的，下证充分性。

显然，这k个集合划分为k个部落，每个部落之间都不会有距离小于ans的点对（否则将置于同一个集合）

如果集合数大于k，我们将大于k的部分作为一个部落，显然之间也没有距离小于ans的点对，与其它集合也没有。Q.E.D

维护集合，我们可以使用并查集。

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn=1005;
struct UnionFind{
    int fa[maxn];
    UnionFind(){
        for(int i=0;i<maxn;i++)
            fa[i]=i;
    }
    void Clear(){
        for(int i=0;i<maxn;i++)
            fa[i]=i;
    }
    int find(int a){
        if(fa[a]!=a)
            fa[a]=find(fa[a]);
        return fa[a];
    }
    bool Near(int a,int b){
        return find(a)==find(b);
    }
    void Union(int a,int b){
        fa[find(a)]=find(b);
    }
};
struct Point{
    double x,y;
    Point(){
        x=0;
        y=0;
    }
    Point(double x_,double y_){
        x=x_;
        y=y_;
    }
};
Point People[maxn];
bool used[maxn];
UnionFind Tribal;
int n,k;
double Dis(Point a,Point b);
bool CanDivide(double Distance)
{
    Tribal.Clear();
    memset(used,false,sizeof(used));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(Dis(People[i],People[j])<Distance)
                Tribal.Union(i,j);
    for(int i=1;i<=n;i++)
        used[Tribal.find(i)]=true;
    int num=0;
    for(int i=1;i<=n;i++)
        if(used[i])
            num++;
    return num>=k;
}
void Solve()
{
    double l=0,r=0x3f3f3f3f;
    while((r-l)>1e-4){
        double mid=(l+r)/2;
        if(CanDivide(mid+1e-5))
            l=mid+1e-5;
        else
            r=mid;
    }
    printf("%.2lf",l);
}
void Readdata()
{
    freopen("loli.in","r",stdin);
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        double x,y;
        cin>>x>>y;
        People[i]=Point(x,y);
    }
}
void Close()
{
    fclose(stdin);
    fclose(stdout);
}
int main()
{
    Readdata();
    Solve();
    Close();
    return 0;
}
double Dis(Point a,Point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}