@Jerusalem 2016-02-14T12:15:33.000000Z 字数 1534 阅读 1356

### Vol5

JSOI2010 Group
BZOJ1821

#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));}

• 私有
• 公开
• 删除