Description

聰聰研究發現，荒島野人總是過著群居的生活，但是，并不是整個荒島上的所有野人都屬于同一個部落，野人們總是拉幫結派形成屬于自己的部落，不同的部落之間則經常發生爭斗。只是，這一切都成為謎團了——聰聰根本就不知道部落究竟是如何分布的。 不過好消息是，聰聰得到了一份荒島的地圖。地圖上標注了N個野人居住的地點（可以看作是平面上的坐標）。我們知道，同一個部落的野人總是生活在附近。我們把兩個部落的距離，定義為部落中距離最近的那兩個居住點的距離。聰聰還獲得了一個有意義的信息——這些野人總共被分為了K個部落！這真是個好消息。聰聰希望從這些信息里挖掘出所有部落的詳細信息。他正在嘗試這樣一種算法： 對于任意一種部落劃分的方法，都能夠求出兩個部落之間的距離，聰聰希望求出一種部落劃分的方法，使靠得最近的兩個部落盡可能遠離。 例如，下面的左圖表示了一個好的劃分，而右圖則不是。請你編程幫助聰聰解決這個難題。 

Input

Output

輸出一行，為最優劃分時，最近的兩個部落的距離，精確到小數點后兩位。

Sample Input

Sample Output

HINT

Source

JSOI2010第二輪Contest1

思路：

首先，考慮這個距離是具有單調性的，（距離越大，分出來的組越少），那么我們二分這個距離，對于小于這個距離的，分到一組，否則不能分到一組。

對于二分出來的這個距離，分組結束后，統計分組個數，如果分組個數大于等于K個，增大這個二分值，否則減少這個二分值。

對于eps的判定，1e-6是可過的（1e-3有點大沒過去.....）；

維護答案，輸出最終答案即可。

對于這個題的解法，看到網上大部分的最小生成樹的思路更加高效：

①對于一個部落來講，可以是一個點，當然也可以多個點。

②那么我們不妨貪心來做，首先按照邊從小到大排序，接下來對于權值較小的邊開始合并.直到合并到n-k條邊的時候.大集合作為一個部落，之外的那些點每個點作為一個部落的話，此時就有K個部落了，那么這個最近的距離就是接下來的那條邊，那么就第n-k+1條樹邊。

③這個思路也是蠻好的，記錄一下，將問題巧妙轉化，變成求第n-k+1條最小生成樹邊。

Ac代碼（窩寫的二分的）：

#include<stdio.h>#include<string.h>#include<math.h>using namespace std;#define eps 1e-6double x[100200];double y[100200];double dis[1005][1005];int f[1005];int n,m;int find(int a){    int r=a;    while(f[r]!=r)    r=f[r];    int i=a;    int j;    while(i!=r)    {        j=f[i];        f[i]=r;        i=j;    }    return r;}int merge(int a,int b){    int A,B;    A=find(a);    B=find(b);    if(A!=B)    {        f[B]=A;    }}int Slove(double mid){    for(int i=1;i<=n;i++)f[i]=i;    for(int i=1;i<=n;i++)    {        for(int j=1;j<=n;j++)        {            if(dis[i][j]<mid)            {                merge(i,j);            }        }    }    int cnt=0;    for(int i=1;i<=n;i++)    {        if(f[i]==i)cnt++;    }    if(cnt<m)return 1;    else return 0;}int main(){    while(~scanf("%d%d",&n,&m))    {        for(int i=1;i<=n;i++)        {            scanf("%lf%lf",&x[i],&y[i]);        }        for(int i=1;i<=n;i++)        {            for(int j=1;j<=n;j++)            {                dis[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));            }        }        double ans=-1;        double l=0;        double r=1000000000000;        while(r-l>eps)        {            double mid=(l+r)/2;            if(Slove(mid)==1)            {                ans=mid;                r=mid;            }            else l=mid;        }        PRintf("%.2lf/n",ans);    }}