2663: [Beijing wc2012]灵魂宝石
题目：传送门
题解：
又是一道卡精度的题目。
很容易就可以看出单调性啊，如果R越大，选的人就越多，R越小，选的人就越少。
那最小值就直接搞咯。
那么对于最大值...n==k肯定就是无限大啦
否则的话...有点恶心...太菜了
我们换个角度想问题，因为要知道R的最大值，那么在只能选择k个人的情况下，我们只需要知道n-k个人的最大匹配的最小R值就好。
那么反过来，原本是距离<R时建边，现在就改为距离>=R时再建边。。。
精度1e-7...
代码：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define eps 1e-7
using namespace std;
struct node
{
double x,y,next;
}a[];int len,last[];
void ins(int x,int y)
{
len++;a[len].x=x;a[len].y=y;
a[len].next=last[x];last[x]=len;
}
int match[],chw[],t;
bool findmuniu(int x)
{
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(chw[y]!=t)
{
chw[y]=t;
if(match[y]== || findmuniu(match[y]))
{
match[y]=x;
return true;
}
}
}
return false;
}
struct dian
{
double x,y;
}b[];
struct bs
{
double x,y;
}c[];
int n,k;
double dis(double x1,double y1,double x2,double y2){return sqrt(abs((x1-x2)*(x1-x2))+abs((y1-y2)*(y1-y2)));}
int check(double R,int opt)
{
int ans=;
len=;memset(last,,sizeof(last));
if(opt==)
{
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
if(dis(b[i].x,b[i].y,c[j].x,c[j].y)<R)
ins(i,j+n);
memset(match,,sizeof(match));
memset(chw,,sizeof(chw));t=;ans=;
for(int i=;i<=n;i++)
{
t++;
if(findmuniu(i))
ans++;
}
}
else
{
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
if(dis(b[i].x,b[i].y,c[j].x,c[j].y)>=R)
ins(i,j+n);
memset(match,,sizeof(match));
memset(chw,,sizeof(chw));t=;ans=;
for(int i=;i<=n;i++)
{
t++;
if(findmuniu(i))
ans++;
}
}
return ans;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++)scanf("%lf%lf",&b[i].x,&b[i].y);
for(int i=;i<=n;i++)scanf("%lf%lf",&c[i].x,&c[i].y);
double l=0.0,r=999999999.9,ans;
while(r-l>=eps)
{
double mid=(l+r)/2.0;
int tt=check(mid,);
if(tt==k)ans=mid;
if(tt>=k)r=mid-eps;
else l=mid+eps;
}
printf("%.2lf\n",ans);
if(n==k){printf("+INF\n");return ;}
l=0.0,r=999999999.9,ans=0.0;
while(r-l>=eps)
{
double mid=(l+r)/2.0;
int tt=check(mid,);
if(tt==n-k)ans=mid;
if(tt<n-k)r=mid-eps;
else l=mid+eps;
}
printf("%.2lf\n",ans);
return ;
}