平面上有m个点，要从这m个点当中找出n个点，使得包含这n个点的圆的半径（圆心为n个点当中的某一点且半径为整数）最小，同
时保证圆周上没有点。
n > m 时要输出-1
样例输入
4
3 2 0 0 1 0 1.2 0
2 2 0 0 1 0
2 1 0 0 1.2 0
2 1 0 0 1 0
样例输出
1
2
1
-1
1 # include <iostream> 2 # include <cstdio> 3 # include <cstring> 4 # include <algorithm> 5 # include <string> 6 # include <cmath> 7 # include <queue> 8 # include <list> 9 # define LL long long 10 using namespace std ; 11 12 double dis[200][200] ; 13 const int INF = 0x3f3f3f3f ; 14 15 struct Point 16 { 17 double x,y; 18 19 }p[200]; 20 21 double dist(Point a,Point b) 22 { 23 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); 24 } 25 26 int main() 27 { 28 //freopen("in.txt","r",stdin) ; 29 int T ; 30 scanf("%d" , &T) ; 31 while(T--) 32 { 33 int m , n ; 34 int i , j ; 35 scanf("%d %d" , &m , &n) ; 36 for (i = 0 ; i < m ; i++) 37 scanf("%lf %lf" , &p[i].x , &p[i].y) ; 38 if (n > m) 39 { 40 printf("-1 ") ; 41 continue ; 42 } 43 int ans = INF ; 44 int r ; 45 memset(dis , 0 , sizeof(dis)) ; 46 for (i = 0 ; i < m ; i++) 47 { 48 for (j = i+1 ; j < m ; j++) 49 { 50 dis[i][j] = dis[j][i] = dist(p[i] , p[j]) ; 51 } 52 sort(dis[i] , dis[i]+m) ; 53 r = (int)dis[i][n-1] ; 54 if (r <= dis[i][n-1]) 55 r += 1 ; 56 if (n < m &&r >= dis[i][n]) 57 continue ; 58 if (r < ans) 59 ans = r ; 60 } 61 if (ans == INF) 62 printf("-1 ") ; 63 else 64 printf("%d " , ans) ; 65 66 } 67 return 0; 68 }