You promised your girlfriend a rounded cake with at least SS strawberries.
But something goes wrong, you don't have the final cake but an infinite plane with NN strawberries on it. And you need to draw a circle which contains strawberries completely to make the cake by yourself.
To simplify the problem, the strawberries are represented as circles in 22D plane. Every strawberry has its center (X_i, Y_i)(Xi,Yi) and the same radius RR.
The cost of your cake is the radius of the circle you draw. So you want to know the minimal cost of the cake, or if you can't give your girlfriend such a cake.
Input
The input file contains several test cases.
The first line of the file is an integer TT, giving the number of test cases. (Tleq20)(T≤20)
For each test case, there are two integers NN and SS in the first line, denoting the number of total strawberries and the number of strawberries on cake as you promised. (1leq N, S leq 300)(1≤N,S≤300)
In the following NN lines, each line contains two integers X_i, Y_iXi,Yi, denoting the coordinates of the strawberry center. (0leq X_i, Y_ileq 10000)(0≤Xi,Yi≤10000)
The next line contains one integer RR, denoting the radius of all strawberries. (1leq R leq 10000)(1≤R≤10000)
It's guaranteed that sum of NN is smaller than 10001000.
Output
Output the minimal cost correct to four decimal places if you can make a rounded cake with at least SSstrawberries, or "The cake is a lie." if not.
样例输入
2
5 3
0 0
0 2
2 0
0 0
1 1
1
1 2
0 0
1
样例输出
1.7071
The cake is a lie.
题意是给你一堆半径相等的圆，让你求一个最小的圆能覆盖其中至少m个圆 首先把他给的圆看成点，然后找个最小的圆覆盖覆盖其中至少m个点，然后答案就是现在找的这个圆的半径加那一堆圆的半径 二分一个答案，以每个点的圆心为圆心，二分的答案为半径画圆，能被覆盖的点必然画出的圆相交。
对这些圆极角排序，然后扫描，圆第一次被扫描到就+1，第二次被扫描到就-1，这个过程中的最大值就是能覆盖的点 意会一下……
#include<bits/stdc++.h> #define eps 0.000000001 using namespace std; const int N=305; int n,m,T; double R; struct Point{ double x,y;}p[N]; struct orz{ double du; int flag;}a[2*N]; bool cmp(orz a,orz b) { if (a.du!=b.du) return a.du<b.du; return a.flag>b.flag; } double dist(Point a,Point b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } double f(Point a,Point b) { return atan2(b.y-a.y,b.x-a.x); } bool check(double x) { int ans=1; for (int i=1;i<=n;i++) { int cnt=0; for (int j=1;j<=n;j++) { if (j==i) continue; if (dist(p[i],p[j])<=2*x) { double mid=f(p[j],p[i]); double xx=acos(dist(p[i],p[j])/2.0/x); a[cnt].du=mid-xx; a[cnt++].flag=1; a[cnt].du=mid+xx; a[cnt++].flag=0; } } sort(a,a+cnt,cmp); int tmp=1; for (int j=0;j<cnt;j++) { if (a[j].flag) tmp++; else tmp--; ans=max(ans,tmp); } } return ans>=m; } int main() { scanf("%d",&T); while (T--) { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y); scanf("%lf",&R); double l=0,r=1e5,ans=-1; for (int i=1;i<=50;i++) { double mid=(l+r)/2.0; if (check(mid)) r=mid,ans=mid; else l=mid; } if (ans<0) printf("The cake is a lie. "); else printf("%.4f ",ans+R); } return 0; }