P7806 [DCOI2021] A 冰魄吐息 题解

hensier · 2021-08-17 18:45:37 · 题解

题目中出现了至多和最小等字眼，因此很有可能需要使用二分答案。

怎么进行二分呢？我们对 d 进行二分并检验当前 d 值是否符合题意。不难发现，如果一个点到原点的距离不超过 d，那么这个点一定符合（所有正比例函数都经过原点）。因此我们只需考虑 x^2+y^2 \gt d^2 的点。

由于到一个点距离不超过 d 的集合就是以该点为圆心，d 为半径的圆内，因此我们只需要求出该圆过原点的两条切线的斜率即可。显然在这两条直线 y=Lx 和 y=Rx 之间（不一定是斜率之间）的所有直线都是符合题意的：

我们只需要找到这 n 个点对应的 L,R 值，将这些点的 [L,R] 抽象成 n 条线段，就可以把问题转化成用最少的点覆盖所有线段的经典贪心问题，并以最少的点数是否小于等于 k 作为二分答案的判断条件。

那么最关键的就是如何求解每个点的 L,R。这里有三种方法：

Solution 1 二分套二分

为什么题目要提供点和直线的距离公式呢？实际上，根据之前插图的演示，不难发现直线与点的距离满足一定的单调性。我们可以利用这个性质再一次二分，得到 L,R 的值。

对于斜率等于 +\infty 的情形，我们可以直接在二分前进行处理，例如将其修改成一个足够大的数。

该做法的时间复杂度为 \mathcal O(n \log x \log x+n \log n \log x)（x 为二分区间大小）：

#include<bits/stdc++.h>
using namespace std;
int n,k;
long double l,r=100000,ans; // 将二分区间右端点 r 调成一个较大的值
struct point
{
    long double x,y;
}p[25001];
struct interval
{
    long double L,R;
    bool operator<(const interval &x)const
    {
        return R<x.R;
    }
}a[25001];
bool check_dis(int x,int y,long double k,long double d)
{
    long double dis=fabs(y-k*x)/sqrt(k*k+1);
    return dis<=d;
}
interval get(point p,long double d)
{
    if(!p.x)return (interval){-p.y/d,p.y/d}; // 特判 x 为 0 的特例
    interval ans;
    long double l=0,r=p.y/p.x; // 第一条切线一定在点 P 的下方
    while(l<=r)
    {
        long double mid=(l+r)*0.5;
        if(check_dis(p.x,p.y,mid,d))
        {
            r=mid-0.00000001; // 第二个二分需要很高的精度，否则无法通过
            ans.L=mid;
        }
        else l=mid+0.00000001;
    }
    l=p.y/p.x,r=100000; // 第二条切线一定在点 P 的上方
    while(l<=r)
    {
        long double mid=(l+r)*0.5;
        if(check_dis(p.x,p.y,mid,d))
        {
            l=mid+0.00000001;
            ans.R=mid;
        }
        else r=mid-0.00000001;
    }
    return ans;
}
bool check(long double d)
{
    int cnt=0;
    for(int i=1;i<=n;++i)
    {
        if(sqrt(p[i].x*p[i].x+p[i].y*p[i].y)<=d)continue; // 不需要考虑到原点距离已经不超过 d 的点
        a[++cnt]=get(p[i],d); // 二分得到斜率区间
    }
    sort(a+1,a+cnt+1); // 排序并用贪心求解
    int tot=0;
    long double tmp=0;
    for(int i=1;i<=cnt;++i)
    {
        if(tmp<=a[i].L)
        {
            tmp=a[i].R;
            if(++tot>k)return false; // 一旦需要的直线数量超过 k 就说明不可行
        }
    }
    return true;
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i)scanf("%Lf%Lf",&p[i].x,&p[i].y);
    while(l<=r)
    {
        long double mid=(l+r)*0.5;
        if(check(mid))
        {
            r=mid-0.0001; // 由于只需要保留两位小数，因此精度可以稍低
            ans=mid;
        }
        else l=mid+0.0001;
    }
    printf("%.2Lf",ans);
    return 0;
}

Solution 2 二分+导角

我们可以通过角和斜率之间的转化求解。

考虑下图的情形（两条直线斜率都非负）：

我们可以用反正切函数求出 PO 与 x 轴正方向的夹角 \alpha，用反正弦函数求出 \beta=\angle TOP。由于两条切线与 OP 之间的夹角相等，因此两条切线与 x 轴正半轴的夹角为 \alpha ± \beta。

我们还需考虑下面两种情形：

这种情形下切线斜率一正一负，而这此时直接把负的当左端点、正的当右端点显然是错误的（有一个跨 0 的过程）。又因为题中没有负坐标，因此只需要保留正斜率。那么：

• 在第一种情形中，符合题意的所有斜率的最小值为其中的正斜率，最大值为 +\infty。
• 在第二种情形中，最小值为 0，最大值为其中的正斜率。

考虑当前的点属于哪一种情形：

• 当切点位于第二象限时（此时 \alpha+\beta \gt 90^\circ），属于第一种。
• 当切点位于第四象限时（此时 \alpha+\beta \lt 90^\circ），属于第二种。

那么，为什么二分套二分的方法不需要对此进行考虑呢？这是因为，我们可以在求解 L,R 时将二分下界设为 0，这样就避免了需要讨论负斜率的情况。

该做法的时间复杂度为 \mathcal O(n \log x+n \log n)：

#include<bits/stdc++.h>
using namespace std;
const double rt=acos(-1)*0.5; // 预处理 90° 弧度制下的值，即 0.5π
int n,k;
long double l,r=100000,ans;
struct point
{
    long double x,y;
}p[25001];
struct interval
{
    long double L,R;
    bool operator<(const interval &x)const
    {
        return R<x.R;
    }
}a[25001];
bool check(long double d)
{
    int cnt=0;
    for(int i=1;i<=n;++i)
    {
        long double x=p[i].x,y=p[i].y;
        if(x*x+y*y<=d*d)continue;
        ++cnt;
        long double alpha,beta;
        alpha=atan(y/x); // 求出 OP 与 x 轴的夹角
        if(!x)alpha=rt; // 如果 x=0 则与 x 轴的夹角为 90°
        beta=asin(d/sqrt(x*x+y*y)); // 求出切线与 OP 连线的夹角
        a[cnt].L=tan(alpha-beta),a[cnt].R=tan(alpha+beta);
        if(a[cnt].L>a[cnt].R)swap(a[cnt].L,a[cnt].R);
        if(a[cnt].L<0)
        {
            if(alpha+beta>rt)
            {
                a[cnt].L=a[cnt].R;
                a[cnt].R=1e18;
            }
            else a[cnt].L=0;
        }
    }
    sort(a+1,a+cnt+1);
    int tot=0;
    long double tmp=0;
    for(int i=1;i<=cnt;++i)
    {
        if(tmp<=a[i].L)
        {
            tmp=a[i].R;
            if(++tot>k)return false;
        }
    }
    return true;
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i)scanf("%Lf%Lf",&p[i].x,&p[i].y);
    while(l<=r)
    {
        long double mid=(l+r)*0.5;
        if(check(mid))
        {
            r=mid-0.0001;
            ans=mid;
        }
        else l=mid+0.0001;
    }
    printf("%.2Lf",ans);
    return 0;
}

Solution 3 二分+导边

借助之前的示意图：

不妨设 T 的坐标为 (a,b)，则 OT 的斜率为 \dfrac{b}{a}，TP 的斜率为 -\dfrac{a}{b}。把 P(x,y) 和 T(a,b) 代入得 \dfrac{b-y}{a-x}=-\dfrac{a}{b}。化简得 a^2+b^2=ax+by。

又因为 TP=d，因此有 (x-a)^2+(y-b)^2=d^2。化简得 a^2+b^2-2ax-2by=d^2-x^2-y^2。

由于 x,y,d 为常数，因此可设 c=d^2-x^2-y^2。

因此

把 (1) 代入 (2) 得

因此我们可以将 b 用 a 进行表示（仅在 y \neq 0 时成立）：

再代回 (1) 得：

最后求出 b_{1,2} 即可得到两条直线的斜率。

特判 y=0 的情形：

此时 OP=x，TP=d，OT=\sqrt{x^2-d^2}。

作 TH \perp OP 于 H，则 \sin \angle TOH=\dfrac{TP}{OP}=\dfrac{TH}{OT}。因此 \dfrac{d}{x}=\dfrac{TH}{\sqrt{x^2-d^2}}，即 TH=\dfrac{d\sqrt{x^2-d^2}}{x}。然后再在 \triangle OTH 中用一次勾股定理即可求出 OH。最后斜率即为 \dfrac{TH}{OH}。

由于 y=0，因此较下方的切线的斜率必然为负。之前提到了本题无需考虑负斜率，因此取斜率的最小值为 0，最大值为 \dfrac{TH}{OH} 即可。