Description

聰聰研究發(fā)現(xiàn)，荒島野人總是過著群居的生活，但是，并不是整個(gè)荒島上的所有野人都屬于同一個(gè)部落，野人們總是拉幫結(jié)派形成屬于自己的部落，不同的部落之間則經(jīng)常發(fā)生爭(zhēng)斗。只是，這一切都成為謎團(tuán)了——聰聰根本就不知道部落究竟是如何分布的。 不過好消息是，聰聰?shù)玫搅艘环莼膷u的地圖。地圖上標(biāo)注了N個(gè)野人居住的地點(diǎn)（可以看作是平面上的坐標(biāo)）。我們知道，同一個(gè)部落的野人總是生活在附近。我們把兩個(gè)部落的距離，定義為部落中距離最近的那兩個(gè)居住點(diǎn)的距離。聰聰還獲得了一個(gè)有意義的信息——這些野人總共被分為了K個(gè)部落！這真是個(gè)好消息。聰聰希望從這些信息里挖掘出所有部落的詳細(xì)信息。他正在嘗試這樣一種算法： 對(duì)于任意一種部落劃分的方法，都能夠求出兩個(gè)部落之間的距離，聰聰希望求出一種部落劃分的方法，使靠得最近的兩個(gè)部落盡可能遠(yuǎn)離。 例如，下面的左圖表示了一個(gè)好的劃分，而右圖則不是。請(qǐng)你編程幫助聰聰解決這個(gè)難題。 

Input

Output

輸出一行，為最優(yōu)劃分時(shí)，最近的兩個(gè)部落的距離，精確到小數(shù)點(diǎn)后兩位。

Sample Input

Sample Output

HINT

Source

JSOI2010第二輪Contest1

思路：

首先，考慮這個(gè)距離是具有單調(diào)性的，（距離越大，分出來(lái)的組越少），那么我們二分這個(gè)距離，對(duì)于小于這個(gè)距離的，分到一組，否則不能分到一組。

對(duì)于二分出來(lái)的這個(gè)距離，分組結(jié)束后，統(tǒng)計(jì)分組個(gè)數(shù)，如果分組個(gè)數(shù)大于等于K個(gè)，增大這個(gè)二分值，否則減少這個(gè)二分值。

對(duì)于eps的判定，1e-6是可過的（1e-3有點(diǎn)大沒過去.....）；

維護(hù)答案，輸出最終答案即可。

對(duì)于這個(gè)題的解法，看到網(wǎng)上大部分的最小生成樹的思路更加高效：

①對(duì)于一個(gè)部落來(lái)講，可以是一個(gè)點(diǎn)，當(dāng)然也可以多個(gè)點(diǎn)。

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

③這個(gè)思路也是蠻好的，記錄一下，將問題巧妙轉(zhuǎn)化，變成求第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);    }}