ACM-ICPC 2018 沈阳赛区网络预赛 E. The cake is a lie（最小圆覆盖至少m个点）

题目链接：

https://nanti.jisuanke.com/t/31446

题意：

给你n个半径都为r的圆（n<=300），用一个大圆至少覆盖s个圆，问大圆的最小半径。

思路：

首先发现问题转化为求覆盖n个点中至少s个点的最小圆的半径，再加r就是答案。

于是就可以二分这个大圆的半径R，以每个点为圆心画圆，看是否有区域被覆盖了s次。

具体思路看知乎：https://www.zhihu.com/question/266750532/answer/312982493

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-8,pi=acos(-1);
int sgn(double x){
    if (x<-eps) return -1;
    if (x>eps) return 1;
    return 0;
}
double fm(double x){
    while(x>pi) x-=2*pi;
    while(x<-pi) x+=2*pi;
    return x;
}
struct P{
    double x,y;
    double len(){
        return sqrt(x*x+y*y);
    }
    bool operator<(const P &t)const{
        return x<t.x||x==t.x&&y>t.y;
    }
    bool operator==(const P &t)const{
        return x==t.x&&y==t.y;
    }
    P operator-(const P &t)const{
        return {x-t.x,y-t.y};
    }
    double slope(){
        return atan2(y,x);
    }
};
double dis(const P &a,const P &b){
    return (a-b).len();
}

const int N=305;
P a[N],stk[N*2];
bool check(int n,int S,double R){
    int ans=0;
    for (int i=1;i<=n;i++){
        int cnt=0;
        int top=0;
        for (int j=1;j<=n;j++){
            if (a[i]==a[j]){
                cnt++;
                continue;
            }
            if (sgn(dis(a[i],a[j])-2*R)>=0) continue;
            double alpha=acos(dis(a[i],a[j])/2/R);
            double k=(a[j]-a[i]).slope();
            double st=fm(k-alpha),ed=fm(k+alpha);
            if (st<ed){
                stk[++top]={st,1};
                stk[++top]={ed,-1};
            }
            else{
                cnt++;
                stk[++top]={ed,-1};
                stk[++top]={st,1};
            }
        }
        sort(stk+1,stk+top+1);
        if (cnt>=S) return 1;
        for (int i=1;i<=top;i++){
            if (stk[i].y<0) cnt--;
            else cnt++;
            if (cnt>=S) return 1;
        }
    }
    return 0;
}
double solve(int n,int S){
    double l=0,r=0; 
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++) r=max(r,dis(a[i],a[j]));
    while(r-l>1e-6){
        double mid=(l+r)/2;
        if (!check(n,S,mid)) l=mid;
        else r=mid;
    }
    return l;
}
int main(){
    int t; scanf("%d",&t);
    while(t--){
        int n,S; scanf("%d%d",&n,&S);
        for (int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);
        double R; scanf("%lf",&R);
        if (S>n) printf("The cake is a lie.\n");
        else printf("%.4f\n",solve(n,S)+R);
    }
}