hiho1227

hiho1227

题目大意：给出M个喂食点，现在我们只能保留N个喂食点。以任意一个喂食点为圆心，任意半径作圆，在圆以内的点都可以留下，但是不能在圆上的出现点，因为管理者不好划分？求最小半径

分析：2015北京网赛签到题？直接暴力，枚举半径，然后枚举每个点为圆心时的情况，记录圆内的点以及圆上的点。

代码：

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;#define eps 1e-7int T, m, n;
int minr;struct P{double x, y;
}p[111];int main() {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);}minr = 1 << 30;for(int k = 1; k <= 1000; k++) {for(int i = 0; i < m; i++){int cnt1 = 1, cnt2 = 0, flag = 0;for(int j = 0; j < m; j++) {if(i != j) {//这里千万不要再写一个求距离的函数，而是直接在求，不然TLE，亲测double d = sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y));if(fabs(k*1.0-d) < eps) cnt2++;if(d < k*1.0) cnt1++;if(cnt2 > 0 || cnt1 > n) { flag = 1; break; }}}if(!flag && cnt1 == n && k < minr) minr = k;}}if(minr == 1 << 30) minr = -1;printf("%d\n", minr);}return 0;
}