【HIHOCODER】The Cats' Feeding Spots

Cats' Feeding Spots"/>

【HIHOCODER】The Cats' Feeding Spots

The Cats’ Feeding Spots

题目链接

• The Cats’ Feeding Spots

题目大意

    给你n个点，现在要你选择一个半径为R的圆，圆心是某个点，然后这个圆中间需要包括n个点，而且在圆上不能有点。

题解

暴力

    首先可以求出每个点距其他点的距离，然后枚举半径即可，复杂度$O(n^2)$

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>using namespace std;struct node
{double x,y;
};
node mp[205];
int T,m,n;
vector<double> v[205];int main()
{scanf("%d",&T);while (T--){memset(mp,0,sizeof(mp));int ans=0x7fffffff;for (int i=0;i<205;i++) v[i].clear();scanf("%d%d",&m,&n);for (int i=0;i<m;i++) scanf("%lf%lf",&mp[i].x,&mp[i].y);for (int i=0;i<m-1;i++)for (int j=i+1;j<m;j++){double l=sqrt( (mp[i].x-mp[j].x)*(mp[i].x-mp[j].x)+(mp[i].y-mp[j].y)*(mp[i].y-mp[j].y) );v[i].push_back(l);v[j].push_back(l);}bool f=0;for (int i=0;i<m;i++) sort(v[i].begin(),v[i].end());for (int i=0;i<m;i++){int r=1,j=0;while (j<m-1){while (r>v[i][j] && j<m-1) j++;if (j>=m-1) break;if (r==v[i][j]) { r++; continue;}if (j+1==n) ans=min(ans,r);r++;}if (n==m) ans=min(ans,r);}if (ans!=0x7fffffff) printf("%d\n",ans);else printf("-1\n");}return 0;
}