hihoCoder1227 The Cats' Feeding Spots 二分

Cats' Feeding Spots 二分"/>

hihoCoder1227 The Cats' Feeding Spots 二分

题目链接：

题目大意：平面上有m个点，要从这m个点当中找出n个点，使得包含这n个点的圆的半径（圆心为n个点当中的某一点且半径为整数）最小，同时保证圆周上没有点。

分析：枚举这m个点，以每个点为圆心找出一个符合条件的半径，然后找出这些半径中的最小值即可。至于如何找出半径，我们可以二分[-1001,1001]区间。

实现代码如下：

#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
#define INF 0x7fffffff
struct POINT
{double x,y;bool operator <(const POINT &a) const{if(x==a.x) return y<a.y;return x<a.x;}
}p[110];
double d[110][110];
int m,n,minr;
bool flag;
int min(int a,int b)
{return a<b?a:b;
}
double dist(POINT a,POINT b)
{return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void init()
{for(int i=0;i<m;i++)for(int j=i;j<m;j++)d[i][j]=d[j][i]=dist(p[i],p[j]);
}
int judge(int cnt,int rad)
{int num=0;flag=true;for(int i=0;i<m;i++){if(d[cnt][i]<rad*1.0) num++;if(d[cnt][i]==rad*1.0) flag=false;}return num;
}
void solve()
{init();minr=INF;for(int i=0;i<m;i++){int l=-1001,r=1001;while(l<=r){int m=(l+r)>>1;int tmp=judge(i,m);if(tmp==n&&flag)  minr=min(minr,m);if(tmp>=n) r=m-1;else l=m+1;}}if(minr==INF) puts("-1");else printf("%d\n",minr);
}
int main()
{int t;scanf("%d",&t);while(t--){scanf("%d%d",&m,&n);for(int i=0;i<m;i++)scanf("%lf%lf",&p[i].x,&p[i].y);sort(p,p+m);solve();}return 0;
}