题解：P5549 [BJ United Round #3] 观察星象

· · 题解

更好的阅读体验

EI 牛逼！

首先很显然有至少一个点在圆上。否则一定可以通过调整使半径缩小。

那么我们枚举在圆上的一个点 p，则由于 r 满足单调性，可以二分。

考虑已知了半径 r 和圆上的一个点 p，要怎么判断是否存在一种画圆的方案使得包含至少 m 个点。那么我们考虑以 p 为端点的直径，对于另外一个点 i，使 i 在圆内的直径的极角一定使一个区间。如图两条红线的夹角即为点 i 所对应的极角区间。

把每个点的区间算出来，扫描线即可找出被最多个区间覆盖的极角。再将覆盖次数和 m 比大小即可。

对于每个 p 去二分，可以做到 O(n^2 \log n \log \frac{V}{\varepsilon})，过不了。

我们知道，对于每个 p 都客观存在着一个 r_i 表示 p 在圆上时，要覆盖 m 个点的最小半径（如果无法覆盖 m 个点则为 +\infty）。

我们还知道，对于一个 1 \sim n 的随机排列，期望有 O(\log n) 个前缀最小值。

考虑元素 x 作为前缀最小值的概率。

上述条件等价于，把 $1 \sim x$ 的数字构成的子序列抽出来，$x$ 排第一个的概率。 显然这个子序列可以看作随机序列，因此 $x$ 作为前缀最小值的概率为 $\frac{1}{x}$。 因此期望前缀最小值个数为 $\sum \limits _{i = 1}^n \frac{1}{i} = O(\ln n)$。

这意味着，如果我们以随机的顺序来枚举 p，只有 O(\log n) 个位置会让答案变小！

具体地，我们使用随机顺序枚举 p，先 check 一下 p 的答案是否会比当前的 ans 小。如果会，我们再进行二分。由上面的分析，我们只会进行 O(\log n) 次二分。

所以总复杂度降到 O(n^2 \log n + n \log^2 n \log \frac{n}{\varepsilon})，其中前一部分是对每个 p check 一次的复杂度，可以通过。

#include<bits/stdc++.h>
#define endl '\n'
#define N 2006
using namespace std;
template <typename T> inline T sq(T x) {return x*x;}
constexpr double eps=5e-8,pi=acos(-1);
int n,m,ord[N],tot;
double x[N],y[N],dis[N][N],ans=2e9;
pair<double,int> b[N<<1];
inline void trans(double &x) {if(x<eps)x+=2*pi;}
inline double get(double cs,double sn) //x, y
{
    if(fabs(cs)<eps&&fabs(sn)<eps)return 0;
    double ret=atan2(sn,cs); trans(ret);
    return ret;
}
int check(double mid,int p)
{
    tot=0;
    for(int i=1;i<=n;i++)
        if(i!=p&&dis[i][p]-mid*2<=eps)
    {
        double t1=get(x[i]-x[p],y[i]-y[p]);
        double t2=acos(dis[i][p]/mid/2);
        b[++tot]={t1-t2,1},b[++tot]={t1+t2,-1};
    }
    sort(b+1,b+1+tot,[](pair<double,int> x,pair<double,int> y) {
         if(fabs(x.first-y.first)<eps*2)return x.second>y.second;
         return x.first<y.first;
    });
    int sum=1,ret=0;
    for(int i=1;i<=tot;i++)
        sum+=b[i].second,ret=max(ret,sum);
    return ret>=m;
}
main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lf%lf",&x[i],&y[i]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)dis[i][j]=sqrt(sq(x[i]-x[j])+sq(y[i]-y[j]));
    for(int i=1;i<=n;i++)ord[i]=i;
    random_shuffle(ord+1,ord+1+n);
    for(int i=1;i<=n;i++)
    {
        if(!check(ans,ord[i]))continue;
        double l=0,r=ans;
        while(r-l>eps)
        {
            double mid=(l+r)/2;
            if(check(mid,ord[i]))r=mid,ans=mid;
            else l=mid;
        }
    }
    printf("%.10lf\n",ans);
    return 0;
}