做网站的意义是什么,浙江建设监理协会官方网站,网站图标怎么上传,怎样做一个app题意#xff1a;
给定m个点#xff0c;然后从这m个点里找到一个点作为圆心#xff0c;求一个最小的半径使得圆内刚好有n个点#xff0c;没有压线的点。
思路#xff1a;
预处理一下各点间的距离#xff0c;暴力枚举圆心#xff0c;然后找到排序后的第n个判断即可。坑…题意
给定m个点然后从这m个点里找到一个点作为圆心求一个最小的半径使得圆内刚好有n个点没有压线的点。
思路
预处理一下各点间的距离暴力枚举圆心然后找到排序后的第n个判断即可。坑点nm的情况要特判一下。
code
#include iostream
#include cstdio
#include algorithm
#include vector
#include cmath
using namespace std;const int N105;
struct node
{/* data */double x,y;void read(){scanf(%lf%lf,x,y);}
}v[N];
vectordouble vt[N];
double cal(node A,node B){return sqrt((A.x-B.x)*(A.x-B.x)(A.y-B.y)*(A.y-B.y));
} int main()
{int T;scanf (%d,T);while (T--){int m,n;scanf (%d%d,m,n);for (int i0;im;i) vt[i].clear();for (int i0;im;i) v[i].read();for (int i0;im;i){for (int j0;jm;j){if (ij) vt[i].push_back(0);else vt[i].push_back(cal(v[i],v[j]));}}if (nm){puts(-1);continue;}int ans0x3f,f0;for (int i0;im;i){sort (vt[i].begin(),vt[i].end());int tt(int) vt[i][n-1] 1;if (ttvt[i][n] nm ) continue;else {ansmin(ans,tt);f1;}//coutansendl;}if (!f) ans-1;cout ans endl;}
}
